开天窗(枚举+贪心):

       大家的电子辞典应该都有开天窗这样的游戏吧。

       现在我们就来讨论一下开天窗的程序。

题目：

Extended Lights Out (zoj 1354)

问题描述：

有一个5行6列的按钮阵列，每个按钮有一盏灯，当它被按下，它和它相邻四个(上下左右)的灯状态改变一次(亮->灭 或灭->亮)。

现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。

问题分析：

v     显然按键是顺序无关的，而且最多按一次(按两次等于不按)。

v     最直接的想法：30个按键，每个有两种操作选择，总共要枚举2^30 ＝1073741824种方案。有点时间复杂度概念的人应该都知道这个方法不行……

v     要想使每一行的灯全灭掉，大家想一下，若第一行的灯的状态告诉你了，你怎样让这第一行灯全灭掉？(只要求这一行)。直观地看，把它的第一行的亮灯下面的开关按一下，上面就应该灭了，这样，把第一行的每个亮灯下面的第二行开关按一下，就可以把第一行亮灯全部干掉……

v     远点看，如果你的第二行开关没有全部干掉第一行的灯，第3,4,5行的开关根本对第一行不起作用，你第一行的灯永远也不会全灭……

v     假设你已经搞定第一行了，可第二行不一定全灭，于是要对第三行的开关操作。

v     后面各行的开关操作都受上一行约束……

v     各行操作完后，上面N-1行的灯应该全灭了，判断最后一行是否全灭，如是则就搞定这题了，否则要考虑改变第一行的开关状态继续往下这样……因为只有第一行不受别行约束……

问题的解决：

v     毫无疑问，搜索之。第1行有6个格，每格点或不点，共2^6＝64种状态。

v     不再是起初凭直觉的遍历1073741824个状态，效率大大提高了。

v     要是按列来考虑，第1列有5个格，搜索2^5＝32个状态就可以了。

源程序:

#include<iostream>
#include<memory>
using namespace std;

int light[5][6];     //灯的状态(１：亮，０：灭)
int flag[5][6];     //作为开关按动的标记，作输出

void press(int x,int y)   //模拟按一个开关时，它的四周的灯的亮灭状况
{        //x,y为开关的坐标
 flag[x][y]=1;
 light[x][y]=1-light[x][y]; //灯状态取反(0->1,1->0)
 if(x<4) light[x+1][y]=1-light[x+1][y];
 if(x>0) light[x-1][y]=1-light[x-1][y];
 if(y>0) light[x][y-1]=1-light[x][y-1];
 if(y<5) light[x][y+1]=1-light[x][y+1];
}

void output()     //输出开关的按动方案，(１：按下，０：不按)
{
 int i,j;
 cout<<endl;
 for(i=0;i<5;i++)
 {for(j=0;j<6;j++)
   cout<<flag[i][j]<<' ';
 cout<<endl;
 }

}

void GO()
{
int i,j,k,x,y;
   int tmp[5][6];
   for(i=0;i<5;i++)   //输入开关初始状态信息
  for(j=0;j<6;j++)
   cin>>tmp[i][j];
   for(k=0;k<64;k++)  //枚举６４种状态
   {
    memcpy(light,tmp,sizeof(light));
    memset(flag,0,sizeof(flag));
    for(i=0;i<6;i++)
   if(k&(1<<i))  //注意是位运算，相当于把k从000000-111111,
//映射到开关的64种不同操作上
    press(0,i);  //枚举第一行的６４种操作
    for(x=1;x<5;x++) //刚才说的规则(其余行操作受上一行灯的状态的约束)
     for(y=0;y<6;y++)
      if(light[x-1][y]==1)
       press(x,y);
    for(i=0;i<6;i++)  //检测最后一行的亮灭状态
     if(light[4][i]==1) //最后一行没全灭，跳到外层，继续……
      break;
    if(i>=6)    //最后一行全灭了！！输出
    {
     output();
     break;
    }  
   }
}

评论