問題文
天海市美术馆馆长 Seth 将决定新的黑白马赛克艺术角的布局。
为了让事情看起来更好,我们希望每件相邻的艺术品都相似。
因此,我决定定义赛斯导演的两件艺术作品之间的差异程度。
白色或黑色的马赛克艺术 M \times N 广场。
考虑将一种马赛克艺术转换为另一种马赛克艺术的操作,并让该操作所需的最小成本为不相似度。
共有三种操作:将黑色方块转换为白色方块,将白色方块转换为黑色方块,以及在四个方向(上、下、左、右)交换相邻方块,并且所有这些操作都有成本。1需要。
请创建一个程序来找出为 Seth 总监提供的两幅马赛克艺术之间的差异程度。
入力
输入将以以下形式从标准输入给出。
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 马赛克艺术。
每行显示每个方块的颜色。 A_{i,j} 由空格分隔。 给出了 N 。
1 第马赛克艺术 i 行目 j 如果该列中的方块是黑色方块, A_{i,j} = 0 ,如果是白色方块 A_{i,j} = 1 。 -
M+2 从行 M 行有
给出了第 2 马赛克艺术。
每行显示每个方块的颜色。 B_{i,j} 由空格分隔。 给出了 N 。
2 第马赛克艺术 i 行目 j 如果该列中的方块是黑色方块, B_{i,j} = 0 ,如果是白色方块 B_{i,j} = 1 。
出力
2两种马赛克艺术的差异程度 如果所有满足1行输出。在输出末尾插入换行符。 如果正确答案是满足
配点
针对此问题设置了部分分数。 满足
- N,\ M \leq{} 10的测试用例都得到正确回答,40 点。
- 如果所有测试用例都回答正确,除了上述之外 50 点。
入力例1
2 2 0 0 1 0 0 0 0 1
出力例1
1
通过交换下面一行的方块,可以以 1 的成本进行转换。
入力例2
3 3 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
出力例2
4
你可以从白色转换为黑色一次,并更改方块 3 次,费用为 4。
入力例3
3 4 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0
出力例3
3
从白色到黑色的转换可以进行两次,并且通过交换方块一次,成本为3。