原题：http://bailian.openjudge.cn/practice/2811/
描述
有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。
在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。
请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道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
解法
有三个关键：
- 每个按钮最多只需按下一次，且按的顺序对结果无影响。
- 第一行中亮的灯，只用按下第二行里对应的按钮，最终看最后一行的结果。
- 只用枚举第一行的按钮情况。可以用数字位运算
我自己的写法：用中间数组存储结果
#include <iostream>
#include <cstring>
using namespace std;
char lights[5][6];
char result[5][6];
char inputs[5][6];
void change(int x, int y) {
lights[x][y] = '0' + (1 - (lights[x][y] - '0'));
result[x][y] = '1';
if (x - 1 >= 0)
lights[x - 1][y] = '0' + (1 - (lights[x - 1][y] - '0'));
if (x + 1 <= 4)
lights[x + 1][y] = '0' + (1 - (lights[x + 1][y] - '0'));
if (y - 1 >= 0)
lights[x][y - 1] = '0' + (1 - (lights[x][y - 1] - '0'));
if (y + 1 <= 5)
lights[x][y + 1] = '0' + (1 - (lights[x][y + 1] - '0'));
}
int main()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 6; j++)
cin >> inputs[i][j];
for (int k = 0; k < (1 << 6); k++) {
memset(result, '0', sizeof(result));
memcpy(lights, inputs, sizeof(inputs));
for (int j = 0; j < 6; j++)
{
int temp = (k >> j) & 1;
if (temp)
change(0, j);
}
for (int i = 1; i <= 4; i++) {
for (int j = 0; j < 6; j++) {
if (lights[i - 1][j] == '1')
change(i, j);
}
}
bool flag = true;
for (int j = 0; j < 6; j++)
{
if (lights[4][j] == '1') {
flag = false;
break;
}
}
if (flag)
break;
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++)
cout << result[i][j] << " ";
cout << endl;
}
}
老师的解法1：只用存一行而不用存整个矩阵。
1 #include <memory>
2 #include <string>
3 #include <cstring>
4 #include <iostream>
5 using namespace std;
6 int GetBit(char c, int i) {
7 // 取c 的第i 位
8 return (c >> i) & 1;
9 }
10 void SetBit(char & c, int i, int v) {
11 // 设置c 的第i 位为v
12 if (v)
13 c |= (1 << i);
14 else
15 c &= ~(1 << i);
16 }
17 void Flip(char & c, int i) {
18 // 将c 的第i 位为取反
19 c ^= (1 << i);
20 }
21 void OutputResult(int t, char result[]) // 输出结果
22 {
23 cout << "PUZZLE #" << t << endl;
24 for (int i = 0; i < 5; ++i) {
25 for (int j = 0; j < 6; ++j) {
26 cout << GetBit(result[i], j);
27 if (j < 5)
28 cout << " ";
29 }
30 cout << endl;
31 }
32 }
33 int main() {
34 char oriLights[5]; // 最初灯矩阵，一个比特表示一盏灯
35 char lights[5]; // 不停变化的灯矩阵
36 char result[5]; // 结果开关矩阵
37 char switchs; // 某一行的开关状态
38 int T;
39 cin >> T;
40 for (int t = 1; t <= T; ++t) {
41 memset(oriLights, 0, sizeof(oriLights));
42 for (int i = 0; i < 5; i++) { // 读入最初灯状态
43 for (int j = 0; j < 6; j++) {
44 int s;
45 cin >> s;
46 SetBit(oriLights[i], j, s);
47 }
48 }
49 for (int n = 0; n < 64; ++n) { // 遍历首行开关的64 种状态
50 memcpy(lights, oriLights, sizeof(oriLights));
51 switchs = n; // 第i 行的开关状态
52 for (int i = 0; i < 5; ++i) {
53 result[i] = switchs; // 第i 行的开关方案
54 for (int j = 0; j < 6; ++j) {
55 if (GetBit(switchs, j)) {
56 if (j > 0)
57 Flip(lights[i], j - 1);// 改左灯
58 Flip(lights[i], j);// 改开关位置的灯
59 if (j < 5)
60 Flip(lights[i], j + 1);// 改右灯
61 }
62 }
63 if (i < 4)
64 lights[i + 1] ^= switchs;// 改下一行的灯
65 switchs = lights[i]; // 第i+1 行开关方案和第i 行灯情况同
66 }
67 if (lights[4] == 0) {
68 OutputResult(t, result);
69 break;
70 }
71 } // for( int n = 0; n < 64; n ++ )
72 }
73 return 0;
74 }
解法2：使用bitset类
1 #include <string>
2 #include <cstring>
3 #include <iostream>
4 #include <bitset>
5 #include <algorithm>
6 using namespace std;
7 void OutputResult(int t, bitset<6> result[]) // 输出结果
8 {
9 cout << "PUZZLE #" << t << endl;
10 for (int i = 0; i < 5; ++i) {
11 for (int j = 0; j < 6; ++j) {
12 cout << result[i][j];
13 if (j < 5)
14 cout << " ";
15 }
16 cout << endl;
17 }
18 }
19 int main() {
20 bitset<6> oriLights[8]; // 最初灯矩阵，一个比特表示一盏灯
21 bitset<6> lights[8]; // 不停变化的灯矩阵
22 bitset<6> result[8]; // 结果开关矩阵
23 bitset<6> switchs; // 某一行的开关状态
24 int T;
25 cin >> T;
26 for (int t = 1; t <= T; ++t) {
27 for (int i = 0; i < 5; i++) { // 读入最初灯状态
28 for (int j = 0; j < 6; j++) {
29 int s;
30 cin >> s;
31 oriLights[i][j] = s;
32 }
33 }
34 for (int n = 0; n < 64; ++n) { // 遍历首行开关的64 种状态
35 copy(oriLights, oriLights + 8, lights);
36 switchs = n; // 第i 行的开关状态
37 for (int i = 0; i < 5; ++i) {
38 result[i] = switchs; // 第i 行的开关方案
39 for (int j = 0; j < 6; ++j) {
40 if (switchs[j]) {
41 if (j > 0)
42 lights[i].flip(j - 1); // 改左灯
43 lights[i].flip(j); // 改开关位置的灯
44 if (j < 5)
45 lights[i].flip(j + 1); // 改右灯
46 }
47 }
48 if (i < 4)
49 lights[i + 1] ^= switchs;// 改下一行的灯
50 switchs = lights[i]; // 第i+1 行开关方案和第i 行灯情况同
51 }
52 if (lights[4] == 0) {
53 OutputResult(t, result);
54 break;
55 }
56 } // for( int n = 0; n < 64; n ++ )
57 }
58 return 0;
59 }