poj 1753 枚举

题目：http://poj.org/problem?id=1753
题意：
有一个4*4的棋盘，棋盘上有黑白格，每一次你可以翻其中的一个格子，这个格子（x，y）如果被翻，那么对应的(x-1,y);(x+1,y);(x,y-1);(x,y+1)格子也会被翻为相对的颜色，让你写一个程序，看最后将棋盘全部翻为白色格子或者是黑色格子用的最少的步数是多少？如果无法把所有格子都翻为白色或者是黑色，那么输出“Impossible”！
分析：
因为每个格子翻转偶数次相当于没翻转，翻转奇数次相当于翻转了一次。所以可以枚举反转的是哪个格子，因为一共就有16个格子，所以总的状态数是1<<16种，用用二进制枚举一下反转的是哪个格子，对每一中状态模拟一下翻转，看看是否可以达到全部是一种颜色的情况。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000001;
char s[4][4];
bool cc[4][4], c[4][4];
int main()
{
    int n;
    //freopen("f.txt","r",stdin);
    for(int i=0;i<4;i++)scanf("%s",s[i]);
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        if(s[i][j]=='b')c[i][j]=1;else c[i][j]=0;
    int ans=17;
    for(int i=0;i<(1<<16);i++){
        int cnt=0;
        for(int i=0;i<4;i++)for(int j=0;j<4;j++)cc[i][j]=c[i][j];
        for(int j=0;j<16;j++){
            if(i&(1<<j)){
                cnt++;
                int ii=j/4,jj=j%4;
                cc[ii][jj]=!cc[ii][jj];
                if(ii-1>=0)cc[ii-1][jj]=!cc[ii-1][jj];
                if(ii+1<4)cc[ii+1][jj]=!cc[ii+1][jj];
                if(jj-1>=0)cc[ii][jj-1]=!cc[ii][jj-1];
                if(jj+1<4)cc[ii][jj+1]=!cc[ii][jj+1];
            }
        }
        int j;
        if(cc[0][0]){
            for(j=1;j<16;j++)if(!cc[j/4][j%4])break;
        }
        else {
            for(j=1;j<16;j++)if(cc[j/4][j%4])break;
        }
        if(j>=16&&cnt<ans){
            ans=cnt;
        }
    }
    if(ans==17)
    printf("Impossible
");
    else printf("%d
",ans);
}

用时235ms，感觉有点慢，因为我在模拟反转操作时是直接对数组操作，网上搜了下题解，发现一个很不错的代码，思路是一样的，但是他把操作和状态保存到整数中，好强啊！但是不好写啊，尤其是把操作保存在cs数组中，可能是对二进制还不太熟练吧，反正我不会这样写。
dizhi:dizhi

#include <iostream>
#define MAX 999999
using namespace std;

char s[4][4];
int cs[16] = {0x13,0x27,78,140,305,626,1252,2248,4880,8992,20032,35968,12544,29184,58368,51200};
int po[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};

int main()
{
    int i,j,value = 0;
    int cmin = MAX;
    char c;
    for(i = 0;i < 16;i++)
    {
        cin >> c;
        if(c == 'b')
            value += (int)po[i];
        else    continue;
    }


    for(i = 0;i < 65536;i++)
    {
        int cou = 0;
        int cvalue = value;
        for(j = 0;j < 16;j++)
            if(i & (int)po[j])
            {
                cou++;
                cvalue ^= cs[j];
            }
        if(cvalue == 0 || cvalue == 65535)
            if(cou < cmin)  cmin = cou;
    }
    if(cmin == MAX) cout << "Impossible";
    else cout << cmin << endl;
   return 0;
}