C - 天下一美術館
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
天下一美術館のセト館長は、新コーナーの白黒のモザイクアートコーナーのレイアウトを決めることになりました。
見栄えを良くするためには、隣同士に並ぶ各アートは似ているものにしたいと考えています。
そこでセト館長の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で変換が可能です。