logo AlgoBeat OnlineJudge
登录 注册

#200947. [USACO07OPEN] 翻转棋 Fliptile S

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

FJ 知道,智商高的奶牛产奶量也大,所以他为奶牛们准备了一个翻动瓦片的益智游戏。

在一个 的方阵上(),每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色,另一面是白色。对一个瓦片翻转,可以让它的颜色由黑到白,或是由白到黑。

然而奶牛们很笨拙,它们翻转一个格子的瓦片时,与其有公共边的所有瓦片也会翻转。

现在奶牛们想知道,至少需要多少次翻转,使所有的瓦片都变成白色朝上呢?

输入格式

第一行两个整数

接下来 行,每行 个整数,表示初始状态, 表示白面朝上, 表示黑面朝上。

输出格式

如果不能将所有瓦片都翻转为白面朝上的话,输出 IMPOSSIBLE

否则输出 行,每行 个整数,第 行的第 个数代表第 行第 列的瓦片被翻转了多少次。

你的输出应该确保翻转次数最少。如果存在多种方案,输出字典序最小的方案。

这里的字典序最小指将输出中的所有空白字符去掉后,形成的字符串字典序最小。

样例

样例输入 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

数据范围与提示

下面的方案操作次数同样是最小的,但是字典序不是最小的。

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