题目大意：有一个冰箱门有16个把手，为4x4正方形排列，要求把所有的把手打开，每次打开或者关闭一个把手的时候，以把手为行列中心的，同一行同一列的把手都会进行状态转换。
回溯要写吐了，都没写出来 代码里是用DFS的步数num作为ans[num]来存的回溯（以后这样写！！！）
#include<cstdio> #include<cstring> #include<algorithm> #include<string.h> #include<iostream> #include<cmath> using namespace std; int map[10][10],flag=0,ans; struct bbq { int x,y; }; bbq a[20]; void change(int x,int y)//把xy的行列全部翻过来 { map[x][y]=!map[x][y]; for(int i=1; i<=4; i++) { map[x][i]=!map[x][i]; map[i][y]=!map[i][y]; } } int judge()//判断是否全部打开 { for(int i=1; i<=4; i++) { for(int j=1; j<=4; j++) { if(map[i][j]==0) return 0; } } return 1; } void dfs(int x,int y,int t) { if(t==ans)//ans是步数，即在这些步里能不能有解，最大是16 { flag=judge(); return ; } if(flag||y>=5)//这里是y》=5，因为下面对x做了约束，这里要约束y。 { return ; } /*int xx=x+(y+1)/5;这里还没有解决 int yy=(y+1)%5; change(x,y); dfs(xx,yy,t+1); a[t].x=x; a[t].y=y; change(x,y); dfs(xx,yy,t);*/ change(x,y);//把xy翻过来的情况 if(x<4) { dfs(x+1,y,t+1); a[t].x=x; a[t].y=y; } else { dfs(1,y+1,t+1); a[t].x=x; a[t].y=y; } change(x,y);//再把xy翻回来 if(x<4) { dfs(x+1,y,t); } else { dfs(1,y+1,t); } } int main() { int i,j; char str;//注意要从1,1开始 for (i = 1; i <= 4; ++i) { for (j = 1; j <= 4; ++j) { scanf("%c", &str); if (str == '-') { map[i][j] = 1; } else { map[i][j] = 0; } } getchar();//度掉回车 } flag=0; for(int i=0; i<=16; i++) { ans=i;//枚举ans dfs(1,1,0); if(flag) { break; } } if(flag) { printf("%d\n",ans); for(int i=0; i<ans; i++) { printf("%d %d\n",a[i].x,a[i].y); } } return 0;//POJ不写这个会编译错误 }