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

#6330
서브태스크

정원 2 4s 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

로그인해야 코드를 작성할 수 있어요.