翻转游戏

Descrption

翻转游戏是在一个 (4 imes 4) 的正方形上进行的，在正方形的 (16) 个格上每个格子都放着一个双面的物件。每个物件的两个面，一面是白色，另一面是黑色，每个物件要么白色朝上，要么黑色朝上，每一轮你只能翻 (3) 至 (5) 个物件，从而由黑到白的改变这些物件上面的颜色，反之亦然。每一轮被选择翻转的物件遵循以下规则：
1. 从 (16) 个物件中任选一个。
2. 翻转所选择的物件的同时，所有与它相邻的左方物件、右方物件、上方物件和下方物件(如果有的话)，都要跟着翻转。
- 以下为例：
```
bwbw
wwww
bbwb
bwwb
```
  - 这里 (b) 表示该格子放的物件黑色面朝上、(w) 表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件，那么格子状态将变为：
```
bwbw
bwww
wwwb
wwwb
```
游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序来求最少的翻转次数来实现这一目标。

Input

输入文件包含 (4) 行，每行 (4) 个字符，每个字符 (w) 或 (b) 表示游戏开始时格子上物件的状态。

Output

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

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

Hint

首先，对于一个位置操作两次以上是不必要的，只有操作/不操作的选择。此题数据范围太水，(16)个格子，完全可以暴力进行(16)个格子的子集枚举。
我们可以想到更加高效的算法：只枚举第一行的方式（(2^4)种），若目标确定，即是想全黑还是全白，则第一行的翻转状态确定了，那么第二行的也就确定了，第二行要想满足要求，第三行的操作方式就确定了。一直到最后一行都可以确定。但这时最后一行的颜色是否满足要求并不确定，再判断一下，如果满足要求就更新答案。

Code

#include <bits/stdc++.h>
const int maxn=4+5,Inf=1<<16;
char str[maxn][maxn];
int ans=Inf;
char tmp[maxn][maxn];
void flip(char &ch){
    if(ch=='w')ch='b';
    else if(ch=='b')ch='w';//必须是else if,不能两个if 
}
int cnt;
void press(int x,int y){
    cnt++;
    flip(tmp[x][y]);//主动翻转第x行第y列，下面是被动翻转
    flip(tmp[x][y+1]);flip(tmp[x][y-1]);
    flip(tmp[x-1][y]);flip(tmp[x+1][y]);
}
void calc(int x,char ch){//目标：全ch 
    memcpy(tmp,str,sizeof(str));//拷贝原数组 
    cnt=0;//计算翻转次数    
    for(int i=1;i<=4;i++)//枚举每一列
        if(x & (1<<(i-1)))
            press(1,i);//第一行第i列需要翻转
    for(int i=2;i<=4;++i){//枚举2~4行
        for(int j=1;j<=4;++j){//枚举每一列
            if(tmp[i-1][j]!=ch)//如果上一行不是ch
                press(i,j); //需要通过下面这个翻转
        }
    }
    for(int i=1;i<=4;++i)//如果第四行有不满足的说明此种方案无效
        if(tmp[4][i]!=ch)return;
    ans=std::min(ans,cnt);
 
}
void Solve(){
    for(int i=1;i<=4;++i)
        scanf("%s",str[i]+1);
    for(int i=0;i<=15;++i){//一行的状态是0~15
        calc(i,'w');//第一行状态为i,变成全w
        calc(i,'b');//第一行状态为i,变成全b
    }
    if(ans==Inf)
        printf("Impossible
");
    else 
        printf("%d
",ans);
}
int main(){    
    Solve();
    return 0;
}