AT_tenka1_2015_qualA_c 天下一美術館

天下一美术馆的馆长 Seto 决定为新展区设计一个黑白马赛克艺术区的布局。 为了让展区更美观，他希望相邻的艺术品尽量相似。 为此，Seto 馆长定义了两幅艺术品之间的“相异度”。 马赛克艺术品由 $M \times N$ 的格子组成，每个格子涂成黑色或白色。 我们考虑将一幅马赛克艺术品转换为另一幅的操作，所需的最小代价即为这两幅艺术品的相异度。 允许的操作有三种，每种操作的代价均为 $1$： - 将黑格变为白格； - 将白格变为黑格； - 交换上下左右相邻的两个格子。 请为 Seto 馆长编写程序，计算给定的两幅马赛克艺术品之间的相异度。

输入从标准输入读入，格式如下： > $M$ $N$ > $A_{1,1}$ $A_{1,2}$ … $A_{1,N}$ > $A_{2,1}$ $A_{2,2}$ … $A_{2,N}$ > … > $A_{M,1}$ $A_{M,2}$ … $A_{M,N}$ > $B_{1,1}$ $B_{1,2}$ … $B_{1,N}$ > $B_{2,1}$ $B_{2,2}$ … $B_{2,N}$ > … > $B_{M,1}$ $B_{M,2}$ … $B_{M,N}$ - 第 $1$ 行输入图片的高度 $M$（$1 \leq M \leq 70$）和宽度 $N$（$1 \leq N \leq 70$），以空格分隔。 - 第 $2$ 行到第 $M+1$ 行描述第一幅马赛克艺术品。每行有 $N$ 个数字 $A_{i,j}$，以空格分隔。若第 $i$ 行第 $j$ 列为黑格，则 $A_{i,j}=0$，为白格则 $A_{i,j}=1$。 - 第 $M+2$ 行到第 $2M+1$ 行描述第二幅马赛克艺术品。每行有 $N$ 个数字 $B_{i,j}$，以空格分隔。若第 $i$ 行第 $j$ 列为黑格，则 $B_{i,j}=0$，为白格则 $B_{i,j}=1$。

输出两幅马赛克艺术品之间的相异度。输出占一行，末尾需换行。

### 配分 本题设有部分分。 - 若能正确解决所有 $N, M \leq 10$ 的测试用例，可得 $40$ 分。 - 若能正确解决所有测试用例，可再得 $50$ 分。 ### 样例解释 1 通过交换下方的格子，可以用代价 $1$ 完成转换。 ### 样例解释 2 通过一次白变黑操作和三次格子交换，可以用代价 $4$ 完成转换。 ### 样例解释 3 通过两次白变黑操作和一次格子交换，可以用代价 $3$ 完成转换。 由 ChatGPT 4.1 翻译