[BOJ 27337] 塗りつぶし (Painting)
View as PDF
Submit solution
Points:
3
Time limit:
2.0s
Memory limit:
1G
Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
JOI くんはお絵かきソフトで遊んでいる．</p>
お絵かきソフトでは，縦 H 行，横 W 列の長方形のマス目に絵を描くことができる．それぞれのマスには色が定められており，色は 1 以上 109 以下の整数で表される．
上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のマスをマス (i,j) と呼ぶ．現在，マス (i,j) の色は Ai,j である．
マス (i,j) から辺で接しているマスへの移動を繰り返し，マス (i,j) と色が異なるマスに入ることなく移動できるマスの集まりを，ここではマス (i,j) の領域と呼ぶ．
お絵かきソフトには，塗りつぶしという機能がある．この機能では，あるマス (x,y) (1 ≦ x ≦ H，1 ≦ y ≦ W) と色 c (1 ≦ c ≦ 109) を指定すると，マス (x,y) の領域に含まれるマスの色がすべて c に変化する．
JOI くんはあるマス (x,y) と色 c を選び，そのマスと色を指定して塗りつぶしをちょうど 1 回使う．塗りつぶしを使った後のマス (x,y) の領域に含まれるマスの個数が JOI くんの得点となる．
JOI くんの得点として達成可能な最大値を求めるプログラムを作成せよ．
입력 형식
入力は以下の形式で与えられる．</p>
H W A1,1 A1,2 … A1,W A2,1 A2,2 … A2,W : AH,1 AH,2 … AH,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 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3예제 출력 2
18예제 입력 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
Comments