Fliptile （二进制压缩）

题目链接：http://poj.org/problem?id=3279

 

题目大意：有一个n*m的棋盘，0表示白色，1表示黑色。每次可以翻转当前位置，它的上下左右四个位置也会被相应翻转。问最少翻转多少次会使所有棋面显示为白色，并给出需要翻转的位置，0表示不翻转，1表示翻转。

 

思路：第一行的翻转状态决定了你第二行的翻转状态。也可以说第n-1行的翻转状态决定了第n行应该如何去翻转。    所以我们可以说第一行起到了决定性的作用

所以我们去枚举第一行的所有的可能的情况。

 

这道题比较巧妙的地方就是它利用了二进制压缩，更加方便的去枚举了第一行的每种情况。

 

首先让我们来学习一下左移<<的概念，其实很好理解，就是将一个数转换为二进制，然后向左移动若干位，然后在多出来的位置上补零，比如，对于5<<2,5的二进制为101，左移两位就是10100，那么最后的结果就是20,。 

利用这个特点，我们可以通过使用一个特殊的数字1，来解决这个枚举问题。枚举的第一步就是确定到底要改变哪几位数，联想到二进制，我们可以这样处理，就题目的测试数据而言，一行有四个数，用一个二进制数xxxx表示，易知，xxxx一共有2^4种排列，其实也是1<<4，之所以这样写，是因为这比pow要快，所以，我们让k从0开始枚举到15，也就是0000到1111，然后规定，只要是带1的位置，就要翻转这个位置的数字，问题又来了，怎么知道哪一位是1,呢，这里还是用到了二进制，即与运算，我们让k分别与1000,0100,0010,0001进行与运算，分别对应不同的位，如果结果不是1，说明这一位上不是0，是不是灰常巧妙，当然，那四个值依然是通过1的左移来计算出来的

具体代码：

 

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int Map[20][20],cal[20][20],out[20][20];
int n,m;
int dir[5][2] = {{0,0},{0,1},{0,-1},{1,0},{-1,0}};

int fuc(int x,int y){       //(x,y)的状态由本身的黑白 + 周围五个的翻转状态决定
    int temp = Map[x][y];

    for(int i = 0;i < 5;i ++){
        int xi = x+dir[i][0];
        int yi = y+dir[i][1];

        if(xi < 1 || xi > n || yi < 1 || yi > m)    continue;
        temp += cal[xi][yi];
    }
    return temp%2;
}
int dfs(){
    for(int i = 2;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(fuc(i-1,j))      //如果上方为黑色，必须要翻转
                cal[i][j] = 1;

    for(int i = 1;i <= m;i ++)      //最后一行全白
        if(fuc(n,i))
            return -1;

    int res = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            res += cal[i][j];
    return res;
}

int main()
{
    while(cin>>n>>m){
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                cin>>Map[i][j];

        int flag = 0;
        int ans = 0x3f3f3f3f;
        for(int i = 0;i < 1<<m;i ++){       //第一行 1<<m种状态，二进制从0开始，字典序从小到大
            memset(cal,0,sizeof(cal));

            for(int j = 1;j <= m;j ++)      //利用二进制枚举第一行所有的情况
                cal[1][m-j+1] = i>>(j-1) & 1;     // cal数组存贮的就是翻转的情况了
            int cont = dfs();
            if(cont >= 0 && cont < ans){        //翻转次数最少
                flag = 1;
                ans = cont;
                memcpy(out,cal,sizeof(cal));
            }
        }
        if(!flag)   cout<<"IMPOSSIBLE"<<endl;
        else{
            for(int i = 1;i <= n;i ++){
                for(int j = 1;j <= m;j ++){
                    if(j != 1)  cout<<" ";
                    cout<<out[i][j];
                }
                cout<<endl;
            }
        }
    }
    return 0;
}