POJ1681画家问题（枚举）采用位运算

POJ 1681
链接： http://poj.org/problem?id=1681

题目大意

每画一个地方，周围上下左右的颜色便随之反转，问需要最少画多少笔才能使墙的颜色都变成黄色。

题目分析

我们假设刚开始所有的墙都是白色的，我们随便在一个地方画一笔（比如就在正中间）那么它上下左右就都变成黄色，我们再在其中一个黄色的周围画一笔，我们会发现刚刚画的那个黄色变成了白色，那么我们就必须再找一个地方将这个位置变成黄色。
有看出点什么吗？
有没有发现，每当你画一格，你的下一笔都会因你之前画的所影响，类似于蝴蝶效应，你现在画的要去解决你之前画的不足，所以每一笔其实都影响着周围。

这里为了逻辑清楚，我将一行当成一个状态，一行中的每一堵强都有画与不画两种选择，一共有n堵墙，就有2^n-1种方案。从而枚举每一种方案。
方案的表示：把画看成是1，不画看成是0，那么n个墙的方案连起来就类似于n位的二进制形式，可以用一个int型（32位）的数字来代替，这样枚举只需一个for循环便可解决。
这样能节省很多代码。

每一种方案就对应着一个数字。
当选第一行的某一种方案时，第一行就与这个数字的每一位进行位运算，最后可以得出第一行墙的结果，然后第二行的方案就会根据第一行哪些墙是白的进行选择，当第二行做完之后代表第一行的墙已经全部变成黄色了，以此类推，当倒数第二行全部变成黄色时，只需观察最后一行是否全部都是黄色，如果不是则说明这种方案不行。

具体代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int wall[20][20]; //记录数据
int tmpwall[20][20];//用来进行操作的数组
void changeColor(int &c)//反转墙的颜色
{
    if(c == 1)
        c = 0;
    else
        c = 1;
}
int main()
{
    int ncase;
    cin >> ncase;
    while(ncase--){
        int n;
        int ans = 1<<30;//无限大
        cin >> n;
        //白色w用 1代替，黄色y用0代替
        for( int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                char c;
                cin >> c;
                if(c == 'w')
                    wall[i][j] = 1;
                else
                    wall[i][j] = 0;
            }
        }
        //第一行一共有2的n次方减1种画画的方法
        //每一个数据method对应着二进制形式就是每行画的状态。
        for(int i = 0; i < (1<<n); ++i)
        {
            int method = i;
            int cnt = 0;//记录次数
            memcpy(tmpwall,wall,sizeof(wall));//复制数组
            for(int j = 0; j < n; ++j)//每一行
            {
                for(int k = 0; k < n; ++k)//每一列
                {
                    if((method >> k)&1)//如果是1代表这个位置有画
                    {
                        cnt++;
                        changeColor(tmpwall[j][k]);
                        if( k > 0)//左边的翻转
                            changeColor(tmpwall[j][k-1]);
                        if( k < n-1)//右边的翻转
                            changeColor(tmpwall[j][k+1]);
                        if( j < n-1)//下面的翻转
                            changeColor(tmpwall[j+1][k]);
                    }
                }
                method = 0;//重置
                for(int m = 0; m < n; ++m)
                {
                    //第二行的画画方法取决于第一行哪些墙还没被画成黄色
                    if(tmpwall[j][m] == 1)
                        method += pow(2,m);
                }
            }
            int sum = 0;
            for(int l = 0; l < n; ++l)
            {
                sum += tmpwall[n-1][l];
                //cout<<tmpwall[n-1][l]<<" ";
            }
           // cout<<endl;
            if(!sum)
                if(cnt < ans)
                {
                    ans = cnt;
                    break;
                }
        }
        if(ans < 1<<30)
            cout << ans << endl;
        else
            cout <<"inf"<<endl;

    }
    return 0;
}