시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB21151571.429%

문제

JOIG 王国は HW 列のマス目に区切られた長方形の形をしている.上から i 行目 (1 ≦ i ≦ H),左から j 列目 (1 ≦ j ≦ W) のマスをマス (i,j) と呼ぶ.

各マスには標高と呼ばれる整数が定まっている.マス (i,j) の標高は Ai,j である.

JOIG 王国では,王国を縦断する運河を建設することにした.運河の建設は,以下のように行われる.

  • ある整数 k (1 ≦ k < W) を定める.左から k 列目と k+1 列目の間に,王国の上端から下端まで縦断する運河を建設する.

運河を横切らず,辺で接している標高が同じマスへの移動を繰り返すことで相互に移動できるマスの集まりをここでは平地と呼ぶ.国土を管理しやすくするため,平地の個数ができるだけ少なくなるように運河の建設位置を決めたい.

JOIG 王国の地形の情報が与えられたとき,運河を建設した後の JOIG 王国内の平地の個数としてありうる最小値を求めるプログラムを作成せよ.

입력

入力は以下の形式で与えられる.

H W
A1,1 A1,2  A1,W
A2,1 A2,2  A2,W
:
AH,1 AH,2  AH,W

출력

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

제한

  • H ≧ 1
  • W ≧ 2
  • H × W ≦ 500 000
  • 1 ≦ Ai,j ≦ 109 (1 ≦ i ≦ H1 ≦ j ≦ W).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
16

H = 1

220

H ≦ 2

327

H ≦ 200W ≦ 200

447

追加の制約はない.

예제 입력 1

4 4
1 1 1 3
2 2 1 3
2 1 1 3
2 2 2 2

예제 출력 1

4

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 の制約を満たす.

예제 입력 2

5 8
1 2 2 5 5 5 5 5
1 1 2 2 5 6 5 6
1 1 1 1 6 6 5 6
1 1 3 1 1 6 7 6
1 4 1 1 1 6 6 6

예제 출력 2

8

k=1 として運河を建設すると,JOIG 王国は 8 個の平地に分かれる.JOIG 王国内の平地の個数を 7 個以下にすることはできないので,8 を出力する.

この入力は小課題 3, 4 の制約を満たす.

예제 입력 3

1 6
1 1 2 2 3 3

예제 출력 3

3

この入力はすべての小課題の制約を満たす.

예제 입력 4

2 10
1 1 1 1 1 3 3 3 3 4
1 2 1 3 3 3 1 1 3 3

예제 출력 4

6

この入力は小課題 2, 3, 4 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.