D

题目大意

翻瓷砖（姑且认为题目就是这个意思吧）

    农民约翰知道越聪明越快乐的牛产的牛奶越多（神马鬼理论），于是他开始安排牛进行一个智力运动在一个M*N (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) 的网格中，每个网格都有一个正方形的瓷砖组成，当然每块瓷砖都是由黑色和白色两种颜色组成的。

    这个游戏是吧所有的瓷砖都变成白色？？，奶牛在翻转瓷砖的时候会把四周的瓷砖一同翻转过来的，当然奶牛想用最少的步骤来翻转，如果有多种翻转方法，输出字典序最小的那个（矩形的字典序。。。。），如果不能完成翻转，输出IMPOSSIBLE。

通过观察可以看出来一共有 2 ^(M*N)种翻转方式，当然不能一种一种的实验，那样会超时到死的，不过通过观察可以看出来只要第一行的翻转方案确认了，那么下面的也可以知道了，因为如果有一个瓷砖需要翻转，本行翻转方法已经确认，那么一定在同列的下行翻转。这样只需要2^15就够了。

写一下试试吧........

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;

#define maxn 30
const int oo = 0xffffff;

//本身和四周的位置,因为需要保存翻转的方法，所以不改变上层
int dir[4][2] = { {0,0},{0,1},{0,-1},{1,0} };
int G[maxn][maxn], ans[maxn][maxn];
int M, N;

//初始化第0层并且复制图到ans
void Start(int k)
{
    int i, j;

    for(i=N; i>0; i--)
    {
        ans[0][i] = k%2;
        k /= 2;
    }

    for(i=1; i<=M; i++)
    for(j=1; j<=N; j++)
        ans[i][j] = G[i][j];
}
int  OK()//判断翻转后的图是否合法
{
    int i;

    for(i=1; i<=N; i++)
        if(ans[M][i])return 0;

    return 1;
}
//翻转图，并且返回需要翻转的步数，若不能翻转成功则返回-1
int  OverTurn()
{
    int i, j, k, sum=0;

    for(i=1; i<=M; i++)
    for(j=1; j<=N; j++)
    {
        if(ans[i-1][j])
        {
            for(k=0; k<4; k++)
            {
                sum++;
                int ni = i+dir[k][0];
                int nj = j+dir[k][1];

                ans[ni][nj] = !ans[ni][nj];
            }
        }
    }

    if(OK() == 0)
        return -1;

    return sum;
}

int  main()
{
    while(scanf("%d%d", &M, &N) != EOF)
    {
         int i, j, k=pow(2, N);
         int sum = oo, p, q=-1;//sum 需要翻转的步数

         for(i=1; i<=M; i++)
         for(j=1; j<=N; j++)
            scanf("%d", &G[i][j]);

         for(i=0; i<=k; i++)
         {
             Start(i);
             p = OverTurn();

             if(p != -1 && sum > p)
                sum = p, q = i;
         }

         if(q == -1)
            printf("IMPOSSIBLE
");
         else
         {
             Start(q);
             OverTurn();

             for(i=0; i<M; i++)
             for(j=1; j<=N; j++)
                printf("%d%c", ans[i][j], j==N?'
':' ');
         }
    }

    return 0;

}