POJ - 3279

不会做。但是感觉思路挺有意思的

大体的思路是：把第一行状态确定好了，之后的每一行都由前一行决定，也就是之后的所有状态都确定好了，此时枚举第一行的状态，看看根据该情况最后一行是否能符合情况，难点就是状态的压缩，也是比较基础的地方了，主要还是难想，对就是菜。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n, m;
int a[25][25];
int tmp[25][25];
int ans1[25][25];
int d[5][2] = {1, 0, -1, 0, 0, 0, 0, 1, 0, -1};
int judge(int x, int y)
{
    int c = a[x][y];
    for(int i = 0; i < 5; i ++)
    {
        int x1 = x + d[i][0], y1 = y + d[i][1];
        if(1 <= x1 && x1 <= n && 1 <= y1 && y1 <= m)
            c += tmp[x1][y1];
    }
    return c % 2;
}
int calc()
{
    int res = 0;
    for(int i = 2; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
            if(judge(i - 1, j))
                tmp[i][j] = 1;
    }
    for(int i = 1; i <= m; i ++)
        if(judge(n, i)) return -1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res += tmp[i][j];
    return res;
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                scanf("%d", &a[i][j]);
        int ans = -1;
        for(int i = 0; i < (1 << m); i ++)
        {
            memset(tmp, 0, sizeof(tmp));
            for(int j = 1; j <= m; j ++)
                tmp[1][m-j+1] = (i >> (j-1)) & 1;
            int num = calc();
            if(num >= 0 && (ans < 0 || ans > num))
            {
                ans = num;
                memcpy(ans1, tmp, sizeof(tmp));
            }
        }
        if(ans == -1)
                printf("IMPOSSIBLE");
            else
            {
                for(int i = 1; i <= n; i ++)
                    for(int j = 1; j <= m; j ++)
                        if(j == m) printf("%d\n", ans1[i][j]);
                        else printf("%d ", ans1[i][j]);
            }
    }
    return 0;
}