第23回日本情報オリンピック　二次予選

2023年12月15日
情報オリンピック日本委員会

問題文

JOI 庭園は縦 N 行，横 N 列のマス目状に区切られた正方形の形をしている． 上から i 行目 (1 ≦ i ≦ N)，左から j 列目 (1 ≦ j ≦ N) のマスは区画 (i, j) と呼ばれている．

JOI 庭園は土壌にあまり恵まれていないため，各区画には特定の 1 種類の色の花を，最大 1 本しか植えることができない． 具体的には，区画 (i, j) には A_{i, j} = R のとき赤，A_{i, j} = Y のとき黄，A_{i, j} = B のとき青の色の花を最大 1 本しか植えることができない．

ここで，この庭園の管理者である K 理事長は，航空写真を撮った時の見栄えを良くするため，次の手順で花を植えようと思っている．

1. 大きさを表す整数 r を決める．ただし 0 ≦ r ≦ (N-1) ÷ 2 を満たさなければならない．
2. 中心を表す区画 (x, y) を決める．ただし r+1 ≦ x ≦ N-r，r+1 ≦ y ≦ N-r を満たさなければならない．
3. 色 c₀, c₁, c₂, …, c_r をそれぞれ赤・黄・青の中から選んで決める．
4. それぞれの区画 (x', y') について，d = |x'-x| + |y'-y| に応じて以下の規則で花を植える．ただし，|t| は t の絶対値を表す．
   • d ≦ r であるならば，区画 (x', y') には色 c_d の花を植える．
   • d > r であるならば，区画 (x', y') には花を植えない．

庭園の大きさ，各区画に植えることができる花の色の情報が与えられたとき，K 理事長が植えることができる花の数の最大値を求めるプログラムを作成せよ．

制約

• 3 ≦ N ≦ 3 500．
• A_{i, j} は R，Y，B のいずれかである (1 ≦ i ≦ N, 1 ≦ j ≦ N)．
• N は整数である．

小課題

1. (4 点) N = 3．
2. (13 点) N ≦ 50．
3. (17 点) N ≦ 800．
4. (14 点) A_{i, j} ≠ R を満たす (i, j) (1 ≦ i ≦ N, 1 ≦ j ≦ N) は 5 個以下である．
5. (16 点) どの (i, j) (1 ≦ i ≦ N-1, 1 ≦ j ≦ N-1) についても，A_{i, j}，A_{i, j+1}，A_{i+1, j}，A_{i+1, j+1} の中に R が 3 個以上存在する．
6. (36 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A_1,1   A_1,2   …   A_1,N
A_2,1   A_2,2   …   A_2,N
︙
A_N,1   A_N,2   …   A_N,N

出力

K 理事長が植えることができる花の数の最大値を 1 行で出力せよ．

入出力例

入力例 1
3
RYR
YBY
BYY

出力例 1
5

r = 1，(x, y) = (2, 2) とし，c₀ として青，c₁ として黄を選ぶと，下図のように 5 本の花を植えることができる．ただし，背景色は各区画に植えることができる花の色を示している．

6 本以上の花を植える方法は存在しないため，5 を出力する．

この入力例は小課題 1, 2, 3, 6 の制約を満たす．

入力例 2
9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

出力例 2
25

r = 3，(x, y) = (5, 6) とし，c₀ として黄，c₁ として黄，c₂ として赤，c₃ として青を選ぶと，下図のように 25 本の花を植えることができる．ただし，背景色は各区画に植えることができる花の色を示している．

26 本以上の花を植える方法は存在しないため，25 を出力する．

この入力例は小課題 2, 3, 6 の制約を満たす．

入力例 3
6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

出力例 3
1

この入力例は小課題 2, 3, 6 の制約を満たす．

入力例 4
20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR

出力例 4
85

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．

入力例 5
10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

出力例 5
25

この入力例は小課題 2, 3, 5, 6 の制約を満たす．