← 返回题目列表

AtCoder · tenka1_2015_qualA_c

C. 天海市美术馆

中文机器翻译题面 查看原题

問題文

天海市美术馆馆长 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。