AT_joig2023_e 運河 (Canal)

JOIG 王国は $ H $ 行 $ W $ 列のマス目に区切られた長方形の形をしている．上から $ i $ 行目 ( $ 1 \leqq i \leqq H $ )，左から $ j $ 列目 ( $ 1 \leqq j \leqq W $ ) のマスをマス $ (i,j) $ と呼ぶ． 各マスには標高と呼ばれる整数が定まっている．マス $ (i,j) $ の標高は $ A_{i,j} $ である． JOIG 王国では，王国を縦断する運河を建設することにした．運河の建設は，以下のように行われる． - ある整数 $ k $ ( $ 1 \leqq k < W $ ) を定める．左から $ k $ 列目と $ k+1 $ 列目の間に，王国の上端から下端まで縦断する運河を建設する． 運河を横切らず，辺で接している標高が同じマスへの移動を繰り返すことで相互に移動できるマスの集まりをここでは**平地**と呼ぶ．国土を管理しやすくするため，平地の個数ができるだけ少なくなるように運河の建設位置を決めたい． JOIG 王国の地形の情報が与えられたとき，運河を建設した後の JOIG 王国内の平地の個数としてありうる最小値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ H $ $ W $ $ A_{1,1} $ $ A_{1,2} $ $ \cdots $ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $ \cdots $ $ A_{2,W} $ $ \vdots $ $ A_{H,1} $ $ A_{H,2} $ $ \cdots $ $ A_{H,W} $

運河を建設した後の JOIG 王国内の平地の個数としてありうる最小値を出力せよ．

### 小課題 1. ( $ 6 $ 点) $ H = 1 $ ． 2. ( $ 20 $ 点) $ H \leqq 2 $ ． 3. ( $ 27 $ 点) $ H \leqq 200 $ ， $ W \leqq 200 $ ． 4. ( $ 47 $ 点) 追加の制約はない． ### Sample Explanation 1 $ k=3 $ として運河を建設すると，JOIG 王国は以下のように $ 4 $ 個の平地に分かれる． - マス $ (1,1) $ ， $ (1,2) $ ， $ (1,3) $ ， $ (2,3) $ ， $ (3,2) $ ， $ (3,3) $ からなる平地 - マス $ (2,1) $ ， $ (2,2) $ ， $ (3,1) $ ， $ (4,1) $ ， $ (4,2) $ ， $ (4,3) $ からなる平地 - マス $ (1,4) $ ， $ (2,4) $ ， $ (3,4) $ からなる平地 - マス $ (4,4) $ からなる平地 JOIG 王国内の平地の個数を $ 3 $ 個以下にすることはできないので， $ 4 $ を出力する． この入力は小課題 $ 3, 4 $ の制約を満たす． ### Sample Explanation 2 $ k=1 $ として運河を建設すると，JOIG 王国は $ 8 $ 個の平地に分かれる．JOIG 王国内の平地の個数を $ 7 $ 個以下にすることはできないので， $ 8 $ を出力する． この入力は小課題 $ 3, 4 $ の制約を満たす． ### Sample Explanation 3 この入力はすべての小課題の制約を満たす． ### Sample Explanation 4 この入力は小課題 $ 2, 3, 4 $ の制約を満たす． ### Constraints - $ H \geqq 1 $ ． - $ W \geqq 2 $ ． - $ H \times W \leqq 500\,000 $ ． - $ 1 \leqq A_{i,j} \leqq 10^9 $ ( $ 1 \leqq i \leqq H $ ， $ 1 \leqq j \leqq W $ )． - 入力される値はすべて整数である．