例题
有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。
Input:
5行组成，每一行包括6个数字（0或1）。相邻两个数字之间用单个空格隔开。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的
Output:
5行组成，每一行包括6个数字（0或1）。相邻两个数字之间用单个空格隔开。其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。
解题思路
注意到此类问题的三个性质：
- 每个位置至多被点击一次
- 点击顺序不影响最终结果
- 固定第一行后，满足题意的方案至多有一种
性质三的分析：当第i行某一位为1时，若前i行已经固定，只能点击第i+1行同一列的位置使得1变为0，从上到下对行使用归纳法即可得到性质。
采用枚举的方法，先枚举第一行的所有点击方式，之后不断使用性质三，到最后一行时判断是否全为0，然后可进行回溯
Tip1
第一行的点击方式可用位运算枚举，枚举0~63，若(k>>(j-1))&1, 点击(1,j)
Tip2
可以适当地开大数组，避免边角越界or特判
AC Code
C++ AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using namespace std;
int map[7][8];
int cp[7][8];
int ans[7][8];
inline void reset(){
for(int i=1;i<=5;i++){
for(int j=1;j<=6;j++){
map[i][j]=cp[i][j];
ans[i][j]=0;
}
}
}
inline void set(int i,int j){
int x[]={i-1,i,i,i,i+1};
int y[]={j,j,j+1,j-1,j};
for(int k=0;k<=4;k++){
map[x[k]][y[k]]=1-map[x[k]][y[k]];
}
ans[i][j]=1;
}
int main(){
for(int i=1;i<=5;i++){
for(int j=1;j<=6;j++){
cin>>map[i][j];
cp[i][j]=map[i][j];
}
}
for(int k=0;k<=63;k++){
for(int j=1;j<=6;j++){
if((k>>(j-1))&1){
set(1,j);
}
}
for(int i=1;i<=4;i++){
for(int j=1;j<=6;j++){
if(map[i][j]==1){
set(i+1,j);
}
}
}
bool flag=true;
for(int j=1;j<=6;j++){
if(map[5][j]==1){
flag=false;
break;
}
}
if(flag)break;
else reset();
}
for(int i=1;i<=5;i++){
for(int j=1;j<=6;j++){
cout<<ans[i][j]<<' ';
}
cout<<endl;
}
}