페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6330
서브태스크

정원 2 4초 1024MB

문제

정원은 세로 N 행, 가로 N 열의 격자판 모양으로 단락 지어진 정사각형의 형태를 하고 있다. 위에서 i 번째 행, 왼쪽에서 j 번째 열의 칸을 구획 (i, j) 이라고 부른다. (1≤i≤N,\ 1≤j≤N)

정원의 토양은 별로 풍족하지 않기 때문에 각 구획에는 특정한 종류의 색의 꽃을 최대 한 개까지 심을 수 있다. 구체적으로는, 구획 (i, j) 에는 A_{ i, j} = R일 때 빨간색, A_{i, j} = Y일 때 노란색, A_{i, j} = B일 때 파란색의 꽃을 최대 한 개 심을 수 있다.

정원의 관리자는 항공사진을 찍었을 때의 보기 좋게 하기 위해 다음의 순서로 꽃을 심을 것으로 생각하고 있다.

  1. 크기를 나타내는 정수 r을 결정한다. 단, 0 ≤ r ≤ (N-1) ÷ 2 를 만족해야 한다.

  2. 중심을 나타내는 구획 (x, y) 를 결정한다. 그러나 r + 1≤x≤N-r,\ r+1≤y≤N-r 을 만족해야 한다.

  3. 색 c_0 , c_1 , c_2 , ..., c_r을 각각 적색, 노랑, 청색 중에서 선택하여 결정한다.

  4. 각 구획 (x ', y')에 대해 d = | x'-x | + | y'-y | 에 따라 다음 규칙으로 꽃을 심는다. | t | 는 t 의 절대 값을 의미한다.

    • d≤r 이면, 구획 (x', y') 에는 색 c_d의 꽃을 심는다.

    • d> r 이면, 구획 (x', y') 에는 꽃을 심지 않는다.

정원의 크기, 각 구획에 심을 수 있는 꽃의 색의 정보가 주어졌을 때, 정원의 관리자가 심을 수 있는 꽃의 수의 최대치를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 주어진다.

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}

  • 3 \le N \le 3\ 500

  • A_{i, j} 는 R,\ Y,\ B중 하나다 ( 1≤i≤N, 1≤j≤N )

  • N 은 정수다.


출력

첫 줄에 정원 관리자가 심을 수 있는 꽃의 최대 수를 출력한다.


부분문제

번호 점수 조건
#14점

N=3

#213점

N<50

#317점

N<800

#414점

A i, j ≠ R 를 만족하는 (i, j) ( 1 ≤ i ≤ N, 1 ≤ j ≤ N )은 5 개 이하이다.

#516점

모든 (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 개 이상 존재한다

#636점

추가 제한 없음


예제1

입력
3
RYR
YBY
BYY
출력
5

r = 1 , (x, y) = (2, 2)로 설정하고 c_0으로 파란색을, c_1로 노란색을 선택하면 아래 그림과 같이 5 개의 꽃을 심을 수 있다. 배경색은 각 구획에 심을 수 있는 꽃의 색을 나타낸다.

6 개 이상의 꽃을 심는 방법은 존재하지 않으므로 5 를 출력한다.

이 입력 예제는 부분 문제 1, 2, 3, 6 의 제약 조건을 충족한다.


예제2

입력
9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY
출력
25

r = 3 , (x, y) = (5,6)으로 설정하고 c_0으로 노란색, c_1로 노란색, c_2로 빨간색, c_3으로 파란색을 선택하면 아래 그림과 같이 25 개의 꽃을 심을 수 있다. 배경색은 각 구획에 심을 수 있는 꽃의 색을 나타낸다.

26 개 이상의 꽃을 심는 방법이 없으므로 25를 출력한다.

이 입력 예는 부분 문제 2, 3, 6 의 제약 조건을 충족한다.


예제3

입력
6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB
출력
1

예제4

입력
20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
출력
85

예제5

입력
10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR
출력
25

출처

JOI 2024 예선2

역링크