题目描述
农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻转棋。
翻转棋可以分成 M × N 个格子，每个格子有两种颜色，一面是黑的，一面是白的。
一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶牛赢
了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格子有
公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。
请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意义下
最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSIBLE。
输入输出格式
输入格式：
第 1 行：两个整数：M 和 N
第 2 ~ M+1 行：第 i+1 行从左到右依次描述了棋盘第 i 行的颜色，共 N 个整数。 1 代
表黑色， 0 代表白色。
输出格式：
第 1 ~ M 行：每行 N 个整数，分别表示在各个格子上翻转的次数。
输入输出样例
说明
·1 ≤ M, N ≤ 15
思路：搜索
由于第一行的修改方案确定之后，每一行的修改方案就确定了，所以说我们只需要用dfs枚举第一行的修改方案。
而接下来的行数修改的最佳方案是将为1的数的正下方的数进行修改，这样的好处是每行处理完只需要考虑下一行，不需要考虑以上的行数。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; int f[1001][1001],ans[1001][1001],cz[1001][1001],a[1001][1001]; int minn=1000000009; void dfs(int lie){ if(lie>m){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cz[i][j]=a[i][j]; for(int i=1;i<=m;i++) if(f[1][i]){ cz[1][i]^=1;cz[2][i]^=1; cz[1][i+1]^=1;cz[1][i-1]^=1; } for(int i=2;i<=n;i++) for(int j=1;j<=m;j++){ if(cz[i-1][j]==1){ f[i][j]=1;cz[i][j]^=1; cz[i][j+1]^=1;cz[i][j-1]^=1; cz[i+1][j]^=1;cz[i-1][j]^=1; } else f[i][j]=0; } bool pd=false; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(cz[i][j]){ pd=true; break; } if(!pd){ int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f[i][j]) sum++; if(sum>=minn) return; minn=sum; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=f[i][j]; } return; } for(int i=0;i<=1;i++){ f[1][lie]=i; dfs(lie+1); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; dfs(1); if(minn==1000000009){ cout<<"IMPOSSIBLE"; return 0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<ans[i][j]<<" "; cout<<endl; } } /* 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 */