问题描述

约翰为奶牛设计了一个智力游戏，名叫翻转棋。翻转棋分为 N × M 个方格，每格两面，一面黑 色，一面白色。当奶牛翻动一个格子时，它的颜色就会翻转，由黑变白或由白变黑。如果把所有的格 子都翻成白色，就算赢了。 奶牛的蹄子很大，一旦它们翻动某个格子，则和这个格子共享边界的其它格子也会被翻转。约翰 给定了奶牛一个初始局面，用 Bi;j 表示第 i 行第 j 列的格子颜色，Bi;j = 1 表示黑色，Bi;j = 0 表示 白色。请求出用最小步数完成时每个格子翻转的次数，最小步数有多个解时，输出字典序最小的一组，如果不可能完成，则输出‘IMPOSSIBLE'

输入格式

第一行：两个整数 N 和 M，1 ≤ N; M ≤ 15 • 第二行到 N + 1 行：第 i + 1 行有 M 个整数 Bi;1 到 Bi;M，对于所有 1 ≤ j ≤ M，0 ≤ Bi;j ≤ 1

输出格式

共N行，每行M个数，用空格隔开，表示第i行第j个棋子翻转的次数

样例输入

4 4

1 0 0 1

0 1 1 0

0 1 1 0

1 0 0 1

样例输出

0 0 0 0

1 0 0 1

1 0 0 1

0 0 0 0

题解

每个格子只有两种状态，所以翻超过一次是没有意义的；

每个格子被翻后，状态的改变只与格子的位置有关，和格子被翻的先后顺序无关；

m，n值很小，枚举搜索每种情况。

 

按顺序从第一行开始翻，翻了b[i][j]，b[i-1][j] , b[i][j-1] , b[i][j+1] , b[i+1][j]也会被翻，也就是是说要想改变b[i][j]的颜色，不一定要翻b[i][j]，可以通过翻b[i+1][j] 改变b[i][j]的颜色。所以翻完第i行（i<n）的后，第i行可能还有黑色的格子。要使这些格子变成白色，就必须翻这些格子正下方的格子。因此，翻第i行的时候，如果b[i-1][j]是黑的，b[i][j]一定要翻，如果b[i-1][j]是白的，b[i][j]一定不能翻。这样，第i行翻哪些格子由第i-1行的状态决定。以此类推，第1行的状态确定了，接下来n-1行要翻哪些格子也就确定了。而第一行翻哪些格子是随意的，因此，只要搜索第一行的每个格子要不要翻，搜索出一种情况后，把剩下的n-1行也翻过来，翻第i行的时候已经保证第i-1行的每个格子都是白的，所以只要检查第n行的状态就可以判断一种方案是否可行。从可行的方案中找出步数最小的即可。

 

1 #include 
     
       2 int n,m,a[20][20],b[20][20],c[20][20],d[20][20],cnt[20][20],ans=1e9;  3 bool check() 4 { 5     for (int i=1;i<=m;i++) 6       if (a[n][i]) 7         return 0; 8     return 1;     9 }10 void work(int s)11 {12     int i,j;13     for (i=1;i<=n;i++)14       for (j=1;j<=m;j++)15         a[i][j]=b[i][j],16         d[i][j]=c[i][j];17     for (i=2;i<=n;i++)18       for (j=1;j<=m;j++)19         if (a[i-1][j])20         {21             a[i][j]^=1;     d[i][j]++;22         a[i][j-1]^=1; a[i][j+1]^=1; 23         a[i+1][j]^=1; a[i-1][j]^=1;24             s++;25         }26     if (check() && s