题意：一个4*4的围棋棋盘，黑白子随机，每次翻转同时翻转四周的棋子，最少翻转几次使所有棋子同色。
代码，非常漂亮的DFS
#include <cstdio> #include <iostream> using namespace std; int map[10][10]={0};//考虑到要不断翻转，我们用0和1代表棋盘黑白两种颜色，这样翻转就可以用“非”运算符来代替了 int dir[5][2]={{-1,0},{1,0},{0,-1},{0,1},{0,0}}; int sum; bool flag; void flip(int x,int y)//翻转（x,y）及其相邻点 { for(int i=0;i<=4;i++) map[x+dir[i][0]][y+dir[i][1]]=!map[x+dir[i][0]][y+dir[i][1]]; return ; } bool judge()//判断棋盘是否单色 { int i,j; for(i=1;i<=4;i++) for(j=1;j<=4;j++) if(map[i][j]!=map[1][1]) return false; return true; } void dfs(int x,int y,int ans)//ans纪录翻转次数 { if(ans==sum) { flag=judge(); return ; } if(flag||x==5) return ; flip(x,y); if(y<4) dfs(x,y+1,ans+1); else dfs(x+1,1,ans+1); flip(x,y); if(y<4) dfs(x,y+1,ans); else dfs(x+1,1,ans); return ; } int main() { int i,j; char tmp; for(i=1;i<=4;i++) for(j=1;j<=4;j++) { cin>>tmp; if(tmp=='w') map[i][j]=1;//白色记为1，黑色记为0 } for(sum=0;sum<=16;sum++)//枚举16次翻转 { dfs(1,1,0); if(flag) break; } if(flag) printf("%d\n",sum); else puts("Impossible"); return 0; }