总时间限制: 1000ms 内存限制: 65536kB

描述

原题: POJ-1222

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。

POJ 2811 熄灯问题 - 图1

用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。

POJ 2811 熄灯问题 - 图2

请你写一个程序, 确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道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则表示不需要按对应的按钮。

样例输入

  1. 0 1 1 0 1 0
  2. 1 0 0 1 1 1
  3. 0 0 1 0 0 1
  4. 1 0 0 1 0 1
  5. 0 1 1 1 0 0

样例输出

  1. 1 0 1 0 0 1
  2. 1 1 0 1 0 1
  3. 0 0 1 0 1 1
  4. 1 0 0 1 0 0
  5. 0 1 0 0 0 0

思路

我们不需要去枚举每一盏灯的状态.

事实上, 当第一行的开关被确定, 第二行灯的状态也就被确定了.

我们这样做, 先枚举第一行的开关状态: 第一行有6盏灯, 每个灯有2种状态, 一共要枚举 2 = 64 种状态. 先确定第一行开关的状态:

  • 为了让第一行剩下亮着的灯熄灭, 就必须改变第二行的开关;
  • 为了让第二行剩下亮着的灯熄灭, 就必须改变第三行的开关;
  • 以此类推, 只要第一行的的开关状态被确定, 第二行及以后开关的状态都会被确定.
  • 编写程序时, 我们只考虑第 i 行和第 i+1 行的灯与开关的状态, 因为第 i-1 行灯的状态已经由第 i-1 行的开关状态决定了.
  • 当第一行的某种开关方案满足让第5行所有的灯都熄灭, 则第一行的方案是成功的, 直接输出结果; 否则继续枚举.

我们采用位运算的方法来设置数据结构. 一个 char 型有8个bits, 而我们一行只有6盏灯, 所有我们可以用字符数组来表示状态矩阵.

代码

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  5. /* 位运算 */
  6. char srcLight[5];    /* 有5行, 每个元素代表一行矩阵 */
  7. char light[5];       /* 参与运算的灯矩阵 */
  8. char result[5];      /* 开关矩阵 */
  10. int getBit(char c, int i) {  /* 取字符 c 的第 i 个bit */
  11.     return (c >> i) & 0x1;
  12. }
  14. void setBit(char& c, int i, int value) {  /* 设置字符 c 的第 i 位的值为 value */
  15.     if(value)  /* if value is 0x1 */
  16.         c = c | (0x1 << i);
  17.     else       /* if value is 0x0 */
  18.         c = c & ~(0x1 << i);
  19. }
  21. void toggleBit(char& c, int i) {  /* 把字符 c 的第 i 位翻转 */
  22.     c = c ^ (0x1 << i);   /* XOR with 0x1 can toggle a bit */
  23. }
  25. void output(int t, char* result) {
  26.     //cout << "PUZZLE #" << t << endl;
  27.     for(int i = 0; i < 5; i++) {  /* 输出 5 行开关数组 */
  28.         for(int j = 0; j < 6; j++) {
  29.             cout << getBit(result[i], j);  /* 输出第 i 行第 j 列的开关状态 */
  30.             if(j < 5)  cout << " ";        /* j < 5 要加空格 */
  31.         }
  32.         cout << endl;
  33.     }
  34. }
  37. int main() {
  38.     int T = 1;
  39.     //cin >> T;   /* 有 T 组测试数据 */
  40.     for(int t = 1; t <= T; t++) {
  41.         /* 读入原始矩阵 */
  42.         memset(srcLight, 0, sizeof(srcLight));
  43.         for(int i = 0; i < 5; i++) {
  44.             for(int j = 0; j < 6; j++) {
  45.                 int tmp;
  46.                 cin >> tmp;
  47.                 setBit(srcLight[i], j, tmp);
  48.             }
  49.         }
  51.         /* 枚举第一行所以可能的状态 */
  52.         for(int n = 0; n < 64; n++) {  /* n 对应第一行开关所有二进制状态 */
  53.             int switcher = n;  /* switcher 代表当前的开关状态 */
  54.             memcpy(light, srcLight, sizeof(srcLight));
  56.             for(int i = 0; i < 5; i++) {  /* 依次处理每一行的灯 */
  57.                 result[i] = switcher;
  59.                 /* 让第 i 行每一个按下的开关都起作用 */
  60.                 for(int j = 0; j < 6; j++) {
  61.                     if(getBit(switcher, j)) {  /* 如果第 i 行第 j 列的开关被按下 */
  62.                         if(j > 0)  toggleBit(light[i], j - 1);
  63.                         toggleBit(light[i], j);
  64.                         if(j < 5)  toggleBit(light[i], j + 1);
  65.                     }
  66.                 }
  68.                 /* 改变了第 i 行的开关, 会引起第 i+1 行灯状态的改变 */
  69.                 if(i < 4) {
  70.                     light[i + 1] = light[i + 1] ^ switcher;
  71.                 }
  72.                 /* 第 i 行灯的状态, 决定了第 i+1 行开关的状态 */
  73.                 switcher = light[i];
  74.             }
  76.             /* 5行灯都处理完了, 看最后一行的灯有没有全部熄灭 */
  77.             if(light[4] == 0) {
  78.                 output(t, result);
  79.                 break;
  80.             }
  81.         }
  82.     }
  84.     return 0;
  85. }