1753:Flip Game（bfs）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char a[4][4];
 4 int dr[5]= {1,-1,0,0,0};                    //上下左右中5个方向
 5 int dc[5]= {0,0,1,-1,0};
 6 int inf=1024;
 7 void turn(int r,int c) {                    //对(r,c)翻转操作
 8     for(int i=0; i<5; i++) {
 9         int rr=r+dr[i];
10         int cc=c+dc[i];
11         if(rr>3||cc>3||cc<0||rr<0)continue;
12         if(a[rr][cc]==‘b‘)a[rr][cc]=‘w‘;
13         else a[rr][cc]=‘b‘;
14     }
15 }
16 bool check() {                            //判断当前状态是否符合要求
17     for(int i=0; i<4; i++) {
18         for(int j=0; j<4; j++) {
19             if(a[i][j]!=a[0][0])return false;
20         }
21     }
22     return true;
23 }
24 void dfs(int r,int c,int k) {
25     if(check()) {
26         inf=min(inf,k);
27         return ;
28     }
29     if(r==4)return;
30     turn(r,c);                            //翻转
31     if(c==3)dfs(r+1,0,k+1);                //下一个元素，换行 
32     else dfs(r,c+1,k+1);
33     turn(r,c);                            //再翻转相当于没有翻转
34     if(c==3)dfs(r+1,0,k);
35     else dfs(r,c+1,k);
36 }
37 int main() {
38     for(int i=0; i<4; i++) {
39         for(int j=0; j<4; j++) {
40             cin>>a[i][j];
41         }
42     }
43     dfs(0,0,0);
44     if(inf<=16)cout<<inf<<endl;
45     else cout<<"Impossible"<<endl;
46     return 0;
47 }