塗りつぶし (Painting)

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\))．
• 入力される値はすべて整数である．

1. (\(9\) 点) \(H = 1\)．
2. (\(32\) 点) \(H \leqq 30\)，\(W \leqq 30\)，\(A_{i,j} \leqq 5\) (\(1 \leqq i \leqq H\)，\(1 \leqq j \leqq W\))．
3. (\(18\) 点) \(H \leqq 30\)，\(W \leqq 30\)．
4. (\(10\) 点) \(A_{i,j} \leqq 2\) (\(1 \leqq i \leqq H\)，\(1 \leqq j \leqq W\))．
5. (\(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\) 行に出力せよ．

JOI 2023 · JCIOI · CC BY-SA 4.0