翻转游戏

Descrption

翻转游戏是在一个

的正方形上进行的，在正方形的

个物件，从而由黑到白的改变这些物件上面的颜色，反之亦然。每一轮被选择翻转的物件遵循以下规则：

个物件中任选一个。
翻转所选择的物件的同时，所有与它相邻的左方物件、右方物件、上方物件和下方物件(如果有的话)，都要跟着翻转。

以下为例：
```
bwbw
wwww
bbwb
bwwb
```
- 这里

- - 表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件，那么格子状态将变为：
```
bwbw
bwww
wwwb
wwwb
```
游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序来求最少的翻转次数来实现这一目标。

Input

输入文件包含

表示游戏开始时格子上物件的状态。

Output

输出文件仅一个整数，即从给定状态到实现这一任务的最少翻转次数。如果给定的状态就已经实现了目标就输出 0，如果不可能实现目标就输出：

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

Hint

根据数据范围可知，本题可以暴力枚举。
我们枚举第一行转后的状态，通过最终目标进而枚举第2行，进而枚举第3行和第4行，从而分别使上一行合法，因为以后不会影响到上一行了。最后判断第4行

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
const int Inf=1<<16;
int cnt,ans=Inf;
char s[5][5],ss[5][5];
void C(char &a){
    if(a=='w')a='b';
    else if(a=='b')a='w';
}
void F(int x,int y){
    cnt++;//翻转一次次数加1
    C(ss[x][y]);
    C(ss[x-1][y]);
    C(ss[x][y-1]);
    C(ss[x+1][y]);
    C(ss[x][y+1]);
}
void W(int x,char y){//目标是全翻为y
    memcpy(ss,s,sizeof s);//拷贝原数组
    cnt=0;
    for(int i=1;i<=4;++i){//按照形参中规定的第一行翻转后的状态来翻转，枚举第一行每一列
        if(x&(1<<(i-1))){//若该点需翻转（与形参中y不同）
            F(1,i);//就主动翻转
        }
    }
    for(int i=2;i<=4;++i){//枚举2～4行
        for(int j=1;j<=4;++j){//枚举每一列
            if(ss[i-1][j]!=y){//若上一行不是y的话
                F(i,j);//就需要本行这一列来翻转从而是上面的那个字符被动变为y
            }
        }
    }//循环结束后前3行全已经变为y了
    for(int i=1;i<=4;++i){
        if(ss[4][i]!=y)return;
    }
    ans=ans>cnt?cnt:ans;//若都能变为y，则第一行按x状态翻转所需要的步数对最终结果有贡献
}
int main(){
    for(int i=1;i<=4;++i){
        scanf("%s",s[i]+1);
    }
    for(int S=0;S<=15;++S){//因为还要翻转第二行，所以第一行翻转后可能是任意状态，在此枚举
        W(S,'w');W(S,'b');
    }
    if(ans==Inf){
        printf("Impossible
");
    }else printf("%d
",ans);
    return 0;
}