Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
JOI くんはお絵かきソフトで遊んでいる.
お絵かきソフトでは,縦 H 行,横 W 列の長方形のマス目に絵を描くことができる.それぞれのマスには色が定められており,色は 1 以上 10^9 以下の整数で表される.
上から i 行目 (1 \leqq i \leqq H),左から j 列目 (1 \leqq j \leqq W) のマスをマス (i,j) と呼ぶ.現在,マス (i,j) の色は A_{i,j} である.
マス (i,j) から辺で接しているマスへの移動を繰り返し,マス (i,j) と色が異なるマスに入ることなく移動できるマスの集まりを,ここではマス (i,j) の領域と呼ぶ.
お絵かきソフトには,塗りつぶしという機能がある.この機能では,あるマス (x,y) (1 \leqq x \leqq H,1 \leqq y \leqq W) と色 c (1 \leqq c \leqq 10^9) を指定すると,マス (x,y) の領域に含まれるマスの色がすべて c に変化する.
JOI くんはあるマス (x,y) と色 c を選び,そのマスと色を指定して塗りつぶしをちょうど 1 回使う.塗りつぶしを使った後のマス (x,y) の領域に含まれるマスの個数が JOI くんの得点となる.
JOI くんの得点として達成可能な最大値を求めるプログラムを作成せよ.
制約
- 1 \leqq H \leqq 500.
- 1 \leqq W \leqq 500.
- 1 \leqq A_{i,j} \leqq 10^9 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- 入力される値はすべて整数である.
小課題
- (9 点) H = 1.
- (32 点) H \leqq 30,W \leqq 30,A_{i,j} \leqq 5 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- (18 点) H \leqq 30,W \leqq 30.
- (10 点) A_{i,j} \leqq 2 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- (31 点) 追加の制約はない.
入力
入力は以下の形式で与えられる.
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}
出力
JOI くんの得点として達成可能な最大値を 1 行に出力せよ.
入力例 1
4 4 1 2 3 1 2 2 3 1 1 2 3 1 3 3 2 2
出力例 1
9
最初の時点で,マス (2,2) の領域に含まれるマスはマス (1,2), (2,1), (2,2), (3,2) の 4 個である.そのため,マス (2,2) と色 3 を指定して塗りつぶしを使うと,下図のように,これらの 4 マスの色が 3 に変化する.
塗りつぶしを使った後,マス (2,2) の領域に含まれるマスはマス (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2) の 9 個になる.よって,JOI くんの得点は 9 となる.
JOI くんの得点を 10 以上にすることはできないので,9 を出力する.
この入力は小課題 2, 3, 5 の制約を満たす.
入力例 2
2 10 1 2 2 1 3 3 3 3 1 1 1 1 1 1 1 1 1 3 3 3
出力例 2
18
この入力は小課題 2, 3, 5 の制約を満たす.
入力例 3
5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 3
25
この入力は小課題 2, 3, 4, 5 の制約を満たす.