题目链接：http://poj.org/problem?id=1222
题目大意：给一个6*5的矩阵，表示30个灯泡的开关情况，其中0代表关，1代表开。可以认为每个灯上有一个开关，按下开关之后，那个灯以及上下左右的4个灯的开关状态会发生改变。求让所有的灯熄灭的解决方法，最后输出5*6的矩阵，0表示不按那个按钮，1表示按。
一开始听说高斯消元什么的……后来发现没有必要，枚举第一行灯泡的开关情况，然后第2、3、4、5行为了让上一行保持熄灭，都是固定的，最后判断一下最后一行是不是也熄灭就行了。说起来就是模拟+DFS，最多搜2^6次，很容易就过了。
AC代码：
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; int map[6][5]; int ans[6][5]; int buffer[6][5]; bool DFS(int x,int pos) { int i,j; if(pos==4) { for(i=0;i<6;i++) ans[i][pos]=buffer[i][pos-1]; for(i=0;i<6;i++) if(ans[i][pos]) { if(i>=1) buffer[i-1][pos]=buffer[i-1][pos]^1;//改变 buffer[i][pos]= buffer[i][pos]^1; if(i<5) buffer[i+1][pos]= buffer[i+1][pos]^1; } for(j=0;j<6;j++) if(buffer[j][pos]) { for(i=0;i<6;i++) if(ans[i][pos]) { if(i>=1) buffer[i-1][pos]=buffer[i-1][pos]^1;//改变 buffer[i][pos]= buffer[i][pos]^1; if(i<5) buffer[i+1][pos]= buffer[i+1][pos]^1; } return false; } return true; } if(x==6) return DFS(0,pos+1); if(pos==0 || buffer[x][pos-1]==1) { ans[x][pos]=1; if(x>=1) buffer[x-1][pos]=buffer[x-1][pos]^1;//改变 buffer[x][pos]= buffer[x][pos]^1; if(x<5) buffer[x+1][pos]= buffer[x+1][pos]^1; buffer[x][pos+1]=buffer[x][pos+1]^1; if(DFS(x+1,pos)) return true; if(x>=1) buffer[x-1][pos]=buffer[x-1][pos]^1;//变回 buffer[x][pos]= buffer[x][pos]^1; if(x<5) buffer[x+1][pos]= buffer[x+1][pos]^1; buffer[x][pos+1]=buffer[x][pos+1]^1; } if(pos==0 || buffer[x][pos-1]==0) { ans[x][pos]=0; if(DFS(x+1,pos)) return true; } return false; } int main() { // freopen("out.txt","w",stdout); int i,j,a,T,tot=0; cin>>T; while(T--) { for(j=0;j<5;j++) for(i=0;i<6;i++) { scanf("%d",&map[i][j]); buffer[i][j]=map[i][j]; } if(!DFS(0,0)) cout<<"woc?"<<endl; cout<<"PUZZLE #"<<++tot<<endl; for(j=0;j<5;j++) { for(i=0;i<6;i++) printf("%d ",ans[i][j]); cout<<endl; } } }
