题目描述

农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻转棋。

翻转棋可以分成 M × N 个格子，每个格子有两种颜色，一面是黑的，一面是白的。

一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶牛赢了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格子有公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。

请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意义下最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSIBLE。

输入格式

第 1 行：两个整数：M 和 N

第 2 ~ M+1 行：第 i+1 行从左到右依次描述了棋盘第 i 行的颜色，共 N 个整数。 1 代表黑色， 0 代表白色。

输出格式

第 1 ~ M 行：每行 N 个整数，分别表示在各个格子上翻转的次数。

输入输出样例

输入 #1

4 4 	
1 0 0 1 	
0 1 1 0 	
0 1 1 0 	
1 0 0 1

输出 #1

0 0 0 0 	
1 0 0 1 	
1 0 0 1 	
0 0 0 0

说明/提示

·1 ≤ M, N ≤ 15

思路

搜索

由于第一行的修改方案确定之后，每一行的修改方案就确定了，所以说我们只需要用dfs枚举第一行的修改方案。

而接下来的行数修改的最佳方案是将为1的数的正下方的数进行修改，这样的好处是每行处理完只需要考虑下一行，不需要考虑以上的行数。

 

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
const int oo=1e9+9;

int m,n,minn=oo;
int f[N][N],a[N][N];
int cz[N][N],ans[N][N];

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[1][i+1]^=1;
				cz[1][i-1]^=1;
				cz[2][i]^=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++)
			scanf("%d",&a[i][j]);
	dfs(1);
	if(minn==oo) {
		printf("IMPOSSIBLE\n");
		return 0;
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++)
			printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}