题目链接：点击打开链接
题目意思：
4*4棋盘，用b代表黑棋，用w表示白棋，棋盘由b或w组成，问能否经过最小次数ans次翻转，使得棋盘上全为黑棋，或者全为白棋。（翻转的规则为翻转某一棋子，周围4个棋子翻转）
思路：
dfs。对于每一个棋子，我们有两种选择，即翻棋子，和不翻棋子，很自然先翻棋子，回溯时不翻棋子。
有一个问题，如何保证步数是最少的？
有一个思路，我们枚举答案，看是否这个答案能够逆推回到初始状态。
进而，我们想从小到大的枚举答案，倘若在答案所表示的步数下，实现全黑或者全白，那么当前解就是最小解。
题目启示参考我的专题小结：点击打开链接
代码：
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int MAXN = 4; int step; bool flag=false; bool board[MAXN+2][MAXN+2]; const int dx[5] = {0, 0, 0, 1, -1}; const int dy[5] = {0, -1, 1, 0, 0}; bool check(){ for(int i=1; i<5; ++i) for(int j=1; j<5; ++j) if(board[i][j] != board[1][1]) return false; return true; } void flip(int x, int y){ for(int i=0; i<5; ++i){ board[x+dx[i]][y+dy[i]] = !board[x+dx[i]][y+dy[i]]; } } void dfs(int x, int y, int cnt){ if(cnt==step){ flag = check(); return; } if(flag || x>=5) return; //给其他运行的函数返回 flip(x, y); if(y<4) dfs(x, y+1, cnt+1); else dfs(x+1, 1, cnt+1); flip(x, y); if(y<4) dfs(x, y+1, cnt); else dfs(x+1, 1, cnt); } int main(){ char temp; for(int i=1; i<5; ++i){ for(int j=1; j<5; ++j){ //scanf("%c", &temp); cin>>temp; if(temp=='b') board[i][j] = true; else if(temp=='w') board[i][j] = false; } } for(step=0; step<16; ++step){ dfs(1, 1, 0); if(flag) break; } if(!flag) printf("Impossible\n"); else printf("%d\n", step); return 0; }
