G - ツーリスト問題
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
ツーリストさんは 2 つのリストを持っています。
2 つのリストの長さはいずれも N で、i 個目のリストの j 番目は A_{i,j} です。 A_{i,j} は正または負の整数で、0 ではありません。
ツーリストさんはこれらのリストに対して以下のような操作を行おうとしています。
- まず、2 つのリストに含まれる負の整数を全て正の整数に書き換える。このとき、元々同じだった数は同じ数に、異なっていた数は異なった数に書き換えなければならない。
- 次に、縦 2 マス横 N マスのマス目が書かれた紙を用意し、i 行目 j 列目のマスに i 個目のリストの j 番目の数を書き込む。
- 最後に、隣接したマスに異なる数が書き込まれているような辺と外枠をはさみで切る。すると紙はいくつかのピースに分かれるので、その個数を数える。
ツーリストさんは、うまく負の整数を書き換えることで、分かれるピースの個数をできるだけ少なくしようとしています。 紙はいくつのピースに分かれるでしょうか?
制約
- 1≦N≦10^5
- 1≦|A_{i,j}|≦300
入力
入力は以下の形式で標準入力から与えられる。
N A_{1,1} A_{1,2} ... A_{1,N} A_{2,1} A_{2,2} ... A_{2,N}
出力
紙が分かれたときのピースの個数を出力せよ。
入力例 1
5 1 2 1 2 1 -1 -2 -3 -3 -3
出力例 1
5
例えば -1 を 999 に、-2 を 2 に、-3 を 1 に書き換えると下図のようになり、ピース数は最小の 5 個となります。
入力例 2
15 1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1 2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3
出力例 2
9