Description

Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M×NM × N grid (1≤M≤15,1≤N≤15)(1 ≤ M ≤ 15,1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word “IMPOSSIBLE”.

Input

Line 11: Two space-separated integers: MM and NN
Lines 2...M+12...M+1: Line i+1i+1 describes the colors (left to right) of row ii of the grid with NN space-separated integers which are 11 for black and 00 for white。

Output

Lines 1...M1...M: Each line contains NN space-separated integers, each specifying how many times to flip that particular location.

Sample Input

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

Sample Output

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

Translation

有一大块由黑白两色地砖组成的拼图，11代表黑色，00代表白色。每次翻动一块地砖，都会使该地砖及其周围地砖（有完整的边相接的地砖）颜色改变（黑变白，白变黑）。要求用最少的翻动次数，将所有地砖变成白色，输出每一块地砖被翻动的次数，如果有多种方案，按字典序输出。

Idea

首先，一块地砖翻动奇数次产生的效果是相同的，翻动偶数次相当于没有翻动；因此，如果要翻动一块地砖，该地砖被翻动的次数只需要是11。
因此，打印出来的答案就是一个00和11构成的矩阵，每一行都可以看作是一个二进制数。
事实上，当第00行的翻动方案确定后，第11行也随之确定（翻动与第00行黑地砖相邻的地砖），接着第22行也确定……一直递推至第M−1M-1行，这是只需要检查第MM行是否都是白色地砖，如果是白色地砖，则该方案可行。
枚举第一行的所有方案，若找不到一种可行的方案，就输出"IMPOSSIBLE"。
每一行的翻转情况可以看作一个二进制整数数x∈[0,2N−1]x\in [0,2^N-1]（一个都不翻转或全部翻转），对于每一个xx，将其二进制位拆开，如果第jj位为11，则翻转第00行第jj个地砖，题目要求字典序输出，因此第一行的方案要先从00开始枚举。接着一直模拟到M−1M-1行，检查M−1M-1行的合法性，若合法，则视情况更新翻动地砖的最小次数和第一行的方案（在枚举中用一个十进制数表示，模拟中拆成二进制数）。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=20;
int map[N][N],temp[N][N],ans[N][N];
int m,n;
int cnt;
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void flip(int x,int y)
{
	temp[x][y]^=1;
	ans[x][y]=1;//翻转了(x,y) 
	int i;
	for(i=0;i<4;i++)//枚举相邻四个地砖
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<0||ny<0||nx>=m||ny>=n) continue;
		else temp[nx][ny]^=1;
	}
}
bool ok(int x)
{
	memcpy(temp,map,sizeof(temp));//临时数组
	cnt=0;
	int i,j;
	for(j=0;j<n;j++)
	{
		if(x&(1<<(n-1-j))) //检查第j块砖是否要翻转
		{
			flip(0,j);
			cnt++;//总翻转次数增加1
		}
	}
	//模拟剩余的行，上一行相邻块为黑色则翻转。
	for(i=1;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(temp[i-1][j]) 
			{
				flip(i,j);
				cnt++;//总翻转次数增加1
			}
		}
	}
	for(j=0;j<n;j++)//检查最后一行
	{
		if(temp[m-1][j])
		{
			return false;
		}
	}
	return true;
}
void solve()
{
	cin>>m>>n;
	int i,j;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			cin>>map[i][j];
		}
	}
	int least=0x3f3f3f3f;
	int choose=-1;
	for(i=0;i<(1<<n);i++)//翻转组合00000...~11111... 
	{
		if(ok(i))
		{
			if(cnt<least)
			{
				least=cnt;
				choose=i;//记录第一行翻转的组合 
			}
		}
	}
	if(choose!=-1)//没有找到可行的方案则为-1
	{
		memset(ans,0,sizeof(ans));
		//将代表第一行方案最优选择的十进制数choose模拟一遍得到答案 
		ok(choose);
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				cout<<ans[i][j];
				if(j<n-1) putchar(' ');
			}
			putchar('\n');
		}
	}
	else puts("IMPOSSIBLE");
}
int main()
{
	solve();
	return 0;
}