시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 14 | 14 | 14 | 100.000% |
JOI くんはお絵かきソフトで遊んでいる.
お絵かきソフトでは,縦 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 くんの得点として達成可能な最大値を求めるプログラムを作成せよ.
入力は以下の形式で与えられる.
H W A1,1 A1,2 … A1,W A2,1 A2,2 … A2,W : AH,1 AH,2 … AH,W
JOI くんの得点として達成可能な最大値を 1 行に出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 9 | H = 1. |
2 | 32 | H ≦ 30,W ≦ 30,Ai,j ≦ 5 (1 ≦ i ≦ H,1 ≦ j ≦ W). |
3 | 18 | H ≦ 30,W ≦ 30. |
4 | 10 | Ai,j ≦ 2 (1 ≦ i ≦ H,1 ≦ j ≦ W). |
5 | 31 | 追加の制約はない. |
4 4 1 2 3 1 2 2 3 1 1 2 3 1 3 3 2 2
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 10 1 2 2 1 3 3 3 3 1 1 1 1 1 1 1 1 1 3 3 3
18
この入力は小課題 2, 3, 5 の制約を満たす.
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
25
この入力は小課題 2, 3, 4, 5 の制約を満たす.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2022/2023 예선 2 3번