POJ1753 Flip Game

题目：给你44的矩阵，其中b代表黑色块，w代表白色块，每次按一个块对应的上下左右四个格与它本身都会翻转成另一种颜色，问你给出矩阵后能不能使全部块变成黑色或白色，能的话输出操作次数，不能的话输出“Impossible”
思路：枚举，利用*01枚举来解决问题**
我们可以这样想，先设把黑色翻转成白色
（先不管怎么翻第一行）当枚举翻了第一行之后，是不是第一行只受第二行影响了，那如果第一行还有黑色块，那第二行就得在对应的位置翻转才可以令第一行翻转成白色
翻了第一行就知道第二行怎么翻了
以此类推，是不是翻了第二行之后就知道第三行怎么翻了，第三行翻完之后就知道第四行怎么翻了
那么其实只要枚举第一行的情况就好了，第一行只有四个块
那么我们可以利用0表示不翻这个块，1表示翻这个块，利用一个数从0000枚举到1111表示翻与不翻的情况
枚举了第一行之后就可以在第二行之后贪心的把前一行的1都尽量消掉（同时这里也说明了前一行有几个1就要进行几步操作）
最后看最后一行是不是全部翻成白色或全部翻成黑色即可，如果是就记录次数
然后统计最小次数即可
同时在这里也要感谢雨巨的代码让我终于明白了如何实现！
代码：（参考了很多雨巨的代码）

#include <iostream>

using namespace std;
int  a[6]= {0};
int b[6]= {0};
int count1(int x)//数有几个1
{
    int cnt=0;
    while(x)
    {
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}
int solve(int c[])
{
    int st=(1<<4)-1;//从0000按到1111的情况
    int temp[5],j[4];
    int ans=100000000;
    for(int k=0; k<=st; k++)//利用01枚举第一行所有可能按的情况
    {
        for(int i=0; i<4; i++)temp[i]=c[i];//利用中间变量完成操作
        int n=count1(k);//记录一开始第一行按了多少个按钮
        temp[0]^=k;//利用异或来模拟翻转的操作
        temp[0]^=(k>>1);//因为按了一个按钮之后左右都会受影响，所以要左移一次与右移一次
        temp[0]^=((k<<1)&((1<<4)-1));//右移的时候注意要把倒数第5位变成0
        temp[1]^=k;//第一行按了按钮之后下一行也会受到影响
        for(int i=1; i<4; i++)//开始下面几行的操作
        {
            j[i]=temp[i-1];
            n+=count1(j[i]);//上一行有几个1，这一行就要对应的按下按钮（简单的说就是上面的数有1，下面对应的数就要按）所以这样就能记录进行了多少次操作
            temp[i]^=temp[i-1];
            temp[i]^=temp[i-1]>>1;
            temp[i]^=((temp[i-1]<<1)&((1<<4)-1));
            temp[i+1]^=j[i];
        }
        if(temp[3]==0)//如果最后一行变成0了说明全部数都变成0了，就说明了翻转成功
        {
            ans=min(ans,n);
        }
    }
    return ans;
}
int main()
{
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            char c;
            cin>>c;
            if(c=='b')
            {
                a[i]|=1<<j;//利用01去记录状态
            }
            else b[i]|=1<<j;//黑白的情况就分两个数组记录
        }
    }
    int ans=solve(a);//算黑色情况翻转的最少次数
    ans=min(ans,solve(b));//算白色情况翻转的最少次数
    if(ans<100000000)cout<<ans;
    else cout<<"Impossible";
    return 0;
}