문제 설명
JOI 정원은 세로 $N$행, 가로 $N$열의 격자 모양으로 나누어진 정사각형 형태를 하고 있다. 위에서부터 $i$번째 행($1 \le i \le N$), 왼쪽에서부터 $j$번째 열($1 \le j \le N$)의 칸은 구획 $(i, j)$라고 불린다.
JOI 정원은 토양이 그리 좋지 않기 때문에, 각 구획에는 특정한 $1$종류의 색깔의 꽃을 최대 $1$송이밖에 심을 수 없다. 구체적으로 구획 $(i, j)$에는 $A_{i, j} =$ R일 때 빨간색, $A_{i, j} =$ Y일 때 노란색, $A_{i, j} =$ B일 때 파란색 꽃을 최대 $1$송이밖에 심을 수 없다.
여기서 이 정원의 관리자인 K 이사장은 항공 사진을 찍었을 때 보기 좋게 하기 위해 다음 순서로 꽃을 심으려고 한다.
- 크기를 나타내는 정수 $r$를 정한다. 단, $0 \le r \le (N-1) \div 2$를 만족해야 한다.
- 중심을 나타내는 구획 $(x, y)$를 정한다. 단, $r+1 \le x \le N-r$, $r+1 \le y \le N-r$를 만족해야 한다.
- 색 $c_0, c_1, c_2, \dots, c_r$를 각각 빨간색, 노란색, 파란색 중에서 골라 정한다.
- 각 구획 $(x', y')$에 대하여, $d = |x'-x| + |y'-y|$에 따라 다음 규칙으로 꽃을 심는다. 단, $|t|$는 $t$의 절댓값을 나타낸다.
- $d \le r$이라면 구획 $(x', y')$에는 색 $c_d$의 꽃을 심는다.
- $d > r$이라면 구획 $(x', y')$에는 꽃을 심지 않는다.
정원의 크기와 각 구획에 심을 수 있는 꽃의 색깔 정보가 주어졌을 때, K 이사장이 심을 수 있는 꽃의 개수의 최댓값을 구하는 프로그램을 작성하여라.
제약 조건
- $3 \le N \le 3\,500$.
- $A_{i, j}$는
R,Y,B중 하나이다 ($1 \le i \le N, 1 \le j \le N$). - $N$은 정수이다.
서브태스크
- ($4$점) $N = 3$.
- ($13$점) $N \le 50$.
- ($17$점) $N \le 800$.
- ($14$점) $A_{i, j} \neq$
R를 만족하는 $(i, j)$ ($1 \le i \le N, 1 \le j \le N$)는 $5$개 이하이다. - ($16$점) 어떤 $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$)에 대해서도 $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ 중에
R가 $3$개 이상 존재한다. - ($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
출력
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
이 입력 예제는 서브태스크 $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
출력
85
이 입력 예제는 서브태스크 $2, 3, 4, 5, 6$의 제약 조건을 만족한다.
예제 5
입력
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
출력
25
이 입력 예제는 서브태스크 $2, 3, 5, 6$의 제약 조건을 만족한다.