poj3279

题意：有一个n*m的格子，每个格子都有黑白两面（0表示白色，1表示黑色）。我们需要把所有的格子都反转成黑色，每反转一个格子，它上下左右的格子都会跟着反转。请求出用最小步数完成反转时每个格子反转的次数。有多个解时，输出字典序最小的一组。

下面引自挑战内容：
首先，同一个格子翻转两次的话就会恢复原状，所以多次翻转是多余的。此外，翻转的格子的集 合相同的话，其次序是无关紧要的。因此，总共有2NM种翻转的方法。不过这个解空间太大了， 我们需要想出更有效的办法。 不妨先看看左上角的格子。在这里，除了翻转(1,1)之外，翻转(1,2)和(2,1)也可以把这个格子翻 转。
于是不妨先指定好上面一行的翻转方法。此时能够翻转(1,1)的只剩下(2,1)了，所以可以直接判 断(2,1)是否需要翻转。类似地(2,1)~(2,N)都能这样判断，如此反复下去就可以确定所有格子的翻 转方法。后(M,1)~(M,N)如果并非全为白色，就意味着不存在可行的操作方法。
像这样，先确定第一行的翻转方式，然后可以很容易判断这样是否存在解以及解的小步数是多 少，这样将第一行的所有翻转方式都尝试一次就能求出整个问题的小步数。这个算法中上面 一行的翻转方式共有2N种，复杂度为O(MN2N)。
–引自：《挑战》

模型建立: 0.也就是说除了最后一行，上面的所有行的颜色状态都可以由 在上面的一行的状态进行确定（即0-(n-1)行之间的反转来把他确定位0的状态，第n行在这个时候就直接判断是否都为0的状态，是的话就是有效解，然后在取相对优的解）

1. 第一行的状态咱们又可以通过枚举子集来进行找出所有的情况，那么下面的所有行就可以通过迭代以及是否反转 来确定状态。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <stdlib.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int state[25][25];
int en[25][25];
int flip[25][25];
int dir[5][2]={{0,0},{0,1},{1,0},{0,-1},{-1,0}};
int get(int x,int y){
    int cnt=state[x][y];
    for(int i=0;i<5;++i)
    {
        int dx=x+dir[i][0];
        int dy=y+dir[i][1];
        if(dx<0||dx>=n||dy<0||dy>=m)continue;
        cnt+=flip[dx][dy];
    }
    return cnt&1;
}
int clca(){
    for(int i=1;i<n;++i){
        for(int j=0;j<m;++j){
            if(get(i-1,j))
                flip[i][j]=1;
        }
    }
    for(int i=0;i<m;++i){
        if(get(n-1,i))
            return -1;
    }
    int tmp=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            tmp+=flip[i][j];
    return tmp;
}
void solve(){
    int ans=-1;
    //二进制的状态压缩过程,对这道题来讲就是对flip[0]的每一个状态位,都枚举一遍,
    //只要抓住 移位，设置标志位 两个要素也没有那么难.
    for(int i=0;i<1<<m;++i){
        memset(flip,0,sizeof(flip));
        for(int j=0;j<m;++j){
            flip[0][j]=i>>j&1;
        }
        int cnt=clca();//然后这儿进行判断是解的优劣情况
        if(cnt>=0&&(ans<0||ans>cnt)){
             ans=cnt;
             memcpy(en,flip,sizeof(flip));
        }
    }
    if(ans<0){
        printf("IMPOSSIBLE\n");
        return ;
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        printf("%d%c",en[i][j],j+1==m?'\n':' ');
    //printf("%d\n",ans);
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&state[i][j]);
        solve();
    }
    return 0;
}