1813:熄灯问题

#1813:熄灯问题 总时间限制: 1000ms 内存限制: 65536kB 描述 有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。 [](http://media.openjudge.cn/images/2811\_1.jpg) 在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。 [](http://media.openjudge.cn/images/2811\_2.jpg) 请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道1）第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次；2）各个按钮被按下的顺序对最终的结果没有影响；3）对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。 输入 5行组成，每一行包括6个数字（0或1）。相邻两个数字之间用单个空格隔开。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。 输出 5行组成，每一行包括6个数字（0或1）。相邻两个数字之间用单个空格隔开。其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。 样例输入 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 样例输出 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 #题目分析: #第一想法，枚举所有可能的按钮（开关）状态，对每一个状态计算最后灯的情况，看是否熄灭，每个按钮有2种状态，一共有30个开关，则状态数为2的30次方，会超时！ #枚举局部！如果存在某个局部，一旦这个局部的状态被确定，那么剩余其他部分的状态只能是确定的一种！ #怎么局部呢？经过观察，第1行就是这样的一个局部！只要确定了第一行的状态确定之后，作用之后，会导致第1行的某些灯是亮的，某些灯是灭的。！！：要熄灭第一行某个亮着的灯（假设位于第i列）那么唯一的办法就是按下第二行第i列的开关！！（因为第一行的开关已经用过了，而第三行及其后的开关不会影响到第一行） #故为了使第1行的灯全部熄灭，第2行的合理开关状态就是唯一的！依次类推！若第5行的灯没有全部熄灭，则此方案是不合理的，故改变第1行的开关方案。 #如何优化？枚举第一列，状态数是2的5次方。此时可以用一个int类型的变量，从0变到63，第1行的开关有6个，相当于有6个比特的所有0,1组合，这时这个变量的每一个取值就对应每一个开关的状态！ 代码: ```cpp #include <iostream> #include <cstdio> using namespace std; int a[6][8];//初始位置 int init[6][8];//存储按下的按钮 bool guess() //寻找出第一行中的各种取值所对应的结果，再通过数据来判定相应的结果和输出 { for(int i=1; i<5; i++) for(int j=1; j<7; j++) init[i+1][j]=(a[i][j]+init[i][j]+init[i-1][j]+init[i][j-1]+init[i][j+1])%2; //当init[1][j]的取值为1时，init[2][j]位置上的数也为1；反之亦然。 for(int i=1; i<7; i++) //判断最后一行是否熄灭 if((init[5][i-1]+init[5][i]+init[5][i+1]+init[4][i])%2!=a[5][i]) return (false); return (true); } void enumate() // 进行枚举的过程，找出64种可能情况中找出数据中对应的输出 { for(int i=1; i<7; i++) init[1][i]=0; //对第一行进行初始化 while(guess()==false) { init[1][1]++; int i = 1; while(init[1][i]>1) { //找到答案就返回，否则继续进行搜索 init[1][i]=0; i++; init[1][i]++; } } return ; } int main() { for(int i=0; i<6; i++) a[i][0]=0; for(int i=1; i<7; i++) a[0][i]=0; //由于在枚举过程中不会用到a[0]和a[i]两种边界值，因此将其初始化为0 for(int i=1; i<6; i++) for(int j=1; j<7; j++) cin >> a[i][j]; // 开始枚举第一行的64种可能取值 enumate(); // 通过枚举找到正确答案，然后按标准格式输出 for(int i=1; i<6; i++) { for(int j=1; j<7; j++) cout << init[i][j] << " "; cout << endl; } return 0; } ```