A2876. 翻转棋
编程题
提高+/省选-
知识点
题目描述
FJ 知道，智商高的奶牛产奶量也大，所以他为奶牛们准备了一个翻动瓦片的益智游戏。
在一个 $M \times N$ 的方阵上（$1 \leq M,N \leq 15$），每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色，另一面是白色。对一个瓦片翻转，可以让它的颜色由黑到白，或是由白到黑。
然而奶牛们很笨拙，它们翻转一个格子的瓦片时，与其有公共边的所有瓦片也会翻转。
现在奶牛们想知道，至少需要多少次翻转，使所有的瓦片都变成白色朝上呢？
在一个 $M \times N$ 的方阵上（$1 \leq M,N \leq 15$），每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色，另一面是白色。对一个瓦片翻转，可以让它的颜色由黑到白，或是由白到黑。
然而奶牛们很笨拙，它们翻转一个格子的瓦片时，与其有公共边的所有瓦片也会翻转。
现在奶牛们想知道，至少需要多少次翻转，使所有的瓦片都变成白色朝上呢？
输入格式
第一行两个整数 $M,N$。
接下来 $M$ 行，每行 $N$ 个整数，表示初始状态，$0$ 表示白面朝上，$1$ 表示黑面朝上。
接下来 $M$ 行，每行 $N$ 个整数，表示初始状态，$0$ 表示白面朝上，$1$ 表示黑面朝上。
输出格式
如果不能将所有瓦片都翻转为白面朝上的话，输出
否则输出 $M$ 行，每行 $N$ 个整数，第 $i$ 行的第 $j$ 个数代表第 $i$ 行第 $j$ 列的瓦片被翻转了多少次。
你的输出应该确保翻转次数最少。如果存在多种方案，输出字典序最小的方案。
这里的字典序最小指将输出中的所有空白字符去掉后，形成的字符串字典序最小。
IMPOSSIBLE。否则输出 $M$ 行，每行 $N$ 个整数，第 $i$ 行的第 $j$ 个数代表第 $i$ 行第 $j$ 列的瓦片被翻转了多少次。
你的输出应该确保翻转次数最少。如果存在多种方案，输出字典序最小的方案。
这里的字典序最小指将输出中的所有空白字符去掉后，形成的字符串字典序最小。
输入输出样例
输入 #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
说明/提示
下面的方案操作次数同样是最小的，但是字典序不是最小的。
```plain
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
```
```plain
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
```