Problem1636--翻转棋1636: 翻转棋
Time Limit: 1.000 Sec Memory Limit: 128 MB
Submit: 7 Solved: 2
[Submit] [Status] [Web Board] [Creator:]Description
农夫约翰知道,聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏,名叫翻转棋。翻转棋可以分成M × N (1 ≤ M, N ≤ 15)个格子,每个格子有两种颜色,一面是黑的,一面是白的。
一旦翻转某个格子,这个格子的颜色就会颠倒。如果把所有的格子都翻成白的,就算奶牛赢了。然而,奶牛的蹄子很大,一旦它们打算翻转某个格子,这个格子附近(即和这个格子有公共边)的格子也会被翻转。一直翻来翻去也很无聊,奶牛们想最小化必须翻动的次数。
请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个,则输出在字典序意义下最小的那个,如果不可能完成任务,则只要输出一行单词:IMPOSSIBLE。
Input
第一行:两个用空格分开的整数:M和N
第二行到M + 1行:第i + 1行从左至右依次描述了棋盘第i行的的颜色,共记N个用空格分开的整数,1 代表黑色,0 代表白色。
Output
第一行到第M行:每行输出N个用空格分开的整数,表示在这个格子上翻转的次数。
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
HINT
(另外还有一个解是
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
但是这个解在字典序意义下没有样例来得
小)
Source/Category
[Submit] [Status]