POJ 3279 Fliptile

> 给一个N行M列的矩阵，值分别为0和1，每次你可以选择将一个变成相反状态，同时，它周围的四个数也会变为相反状态。 
问：最少翻转多少次，可以将所有值都变成0 
多个解，输出翻转次数最少的（若有次数相同解，输出字典序小的） 
若无解，输出”IMPOSSIBLE”

显然一个数字只能翻转一次，那就按照字典序枚举第一行的所有可能，记录下答案最小的一个。然后每一个数看它上面是否为0，如果是就不管，如果不是就要反转当前的数字。
实现细节还是要注意的，感觉统计当前状态的思路也不错。

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
int dx[5]={0,0,-1,0};
int dy[5]={1,-1,0,0};
int a[25][25];
int f[25][25];
int ans[25][25];
int best=inf;   int m,n;
inline int  Judge(int x,int y){
    int tmp=a[x][y];
    for(int i=0;i<=3;++i){
        int gx=x+dx[i];
        int gy=y+dy[i];
        if(gx<1||gy<1||gx>m||gy>n) continue;
        tmp+=f[gx][gy];
    }
    return tmp&1;
}
int main (){
//  freopen("data.txt","r",stdin);
//  freopen("my.out","w",stdout);   
    while(scanf("%d %d",&m,&n)!=EOF){
        best=inf;
    for(int i=1;i<=m;++i) 
        for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]);
    for(int i=0;i<=(1<<n)-1;++i){
        memset(f,0,sizeof(f));
        for(int j=1;j<=n;++j){
            f[1][n-j+1]=(i>>(j-1))&1;
        }
        for(int k=2;k<=m;++k){
            for(int j=1;j<=n;++j){
                if(Judge(k-1,j))
                    f[k][j]=1;
            }
        }
        int flag=1;
        for(int k=1;k<=n;++k){
            if(Judge(m,k)){
                flag=0;
                break;
            }
        }
        if(flag==1){
            int tmp=0;
            for(int k=1;k<=m;++k){
                for(int j=1;j<=n;++j){
                    tmp+=f[k][j];
                }
            }
            if(tmp<best){
                best=tmp;
                for(int k=1;k<=m;++k){
                    for(int j=1;j<=n;++j){
                        ans[k][j]=f[k][j];
                    }
                }
            }
        }
    }
    if(best==inf){
        printf("IMPOSSIBLE");
    }
    else{
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(j==n)
                    printf("%d\n",ans[i][j]);
                else
                    printf("%d ",ans[i][j]);
            }
        }
    }
}
    return 0;
}
```