天下一プログラマーコンテスト2015予選A

C - 天下一美術館


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

天下一美術館のセト館長は、新コーナーの白黒のモザイクアートコーナーのレイアウトを決めることになりました。

見栄えを良くするためには、隣同士に並ぶ各アートは似ているものにしたいと考えています。

そこでセト館長の2つのアート同士の相違度を定義することにしました。

モザイクアートは白か黒に塗られた M \times N のマス目です。

一方のモザイクアートを他方のモザイクアートに変換する操作を考え、その操作に必要な最小のコストを相違度とします。

操作は、黒マスから白マスへの変換、白マスから黒マスへの変換、上下左右の4方向に隣り合ったマス目の交換の3種類あり、どれもコストが1かかります。

セト館長のために与えられた2つのモザイクアートの相違度を求めるプログラムを作成してください。


入力

入力は以下の形式で標準入力から与えられる。

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

白から黒への変換を1回、マス目の交換を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

白から黒への変換を2回、マス目の交換を1回行うことでコスト3で変換が可能です。


Submit提出する