Enunciado del problema
El jardín JOI tiene la forma de un cuadrado dividido en una cuadrícula de $N$ filas verticalmente y $N$ columnas horizontalmente. La celda en la $i$-ésima fila desde arriba ($1 \le i \le N$) y la $j$-ésima columna desde la izquierda ($1 \le j \le N$) se denomina parcela $(i, j)$.
Como el jardín JOI no cuenta con un suelo muy fértil, en cada parcela solo se puede plantar como máximo $1$ flor de $1$ color específico. Específicamente, en la parcela $(i, j)$ solo se puede plantar como máximo $1$ flor de color rojo cuando $A_{i, j} =$ R, amarillo cuando $A_{i, j} =$ Y y azul cuando $A_{i, j} =$ B.
Aquí, el director K, administrador de este jardín, piensa plantar flores mediante el siguiente procedimiento para que el jardín luzca bien al tomar una fotografía aérea:
- Decidir un número entero $r$ que representa el tamaño. Debe cumplir $0 \le r \le (N-1) \div 2$.
- Decidir una parcela $(x, y)$ que representa el centro. Debe cumplir $r+1 \le x \le N-r$ y $r+1 \le y \le N-r$.
- Elegir y decidir los colores $c_0, c_1, c_2, \dots, c_r$, cada uno entre rojo, amarillo y azul.
- Para cada parcela $(x', y')$, plantar una flor según $d = |x'-x| + |y'-y|$ siguiendo estas reglas, donde $|t|$ denota el valor absoluto de $t$:
- Si $d \le r$, plantar una flor de color $c_d$ en la parcela $(x', y')$.
- Si $d > r$, no plantar ninguna flor en la parcela $(x', y')$.
Dados el tamaño del jardín y la información sobre los colores de las flores que se pueden plantar en cada parcela, escribe un programa para encontrar el número máximo de flores que el director K puede plantar.
Restricciones
- $3 \le N \le 3\,500$.
- $A_{i, j}$ es uno de
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ es un número entero.
Subtareas
- ($4$ puntos) $N = 3$.
- ($13$ puntos) $N \le 50$.
- ($17$ puntos) $N \le 800$.
- ($14$ puntos) Hay como máximo $5$ pares $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) que cumplen $A_{i, j} \neq$
R. - ($16$ puntos) Para cualquier $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), entre $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ existen al menos $3$ ocurrencias de
R. - ($36$ puntos) Sin restricciones adicionales.
Entrada
La entrada se proporciona en el siguiente formato:
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}Salida
Imprime en $1$ línea el número máximo de flores que el director K puede plantar.
Ejemplo 1
Entrada
3 RYR YBY BYY
Salida
5
Si fijamos $r = 1$ y $(x, y) = (2, 2)$, y elegimos azul como $c_0$ y amarillo como $c_1$, podemos plantar $5$ flores como se muestra en la figura de abajo. Aquí, el color de fondo indica el color de la flor que se puede plantar en cada parcela.
Como no hay forma de plantar $6$ o más flores, se imprime $5$.
Este ejemplo de entrada cumple las restricciones de las subtareas $1, 2, 3, 6$.
Ejemplo 2
Entrada
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Salida
25
Si fijamos $r = 3$ y $(x, y) = (5, 6)$, y elegimos amarillo como $c_0$, amarillo como $c_1$, rojo como $c_2$ y azul como $c_3$, podemos plantar $25$ flores como se muestra en la figura de abajo. Aquí, el color de fondo indica el color de la flor que se puede plantar en cada parcela.
Como no hay forma de plantar $26$ o más flores, se imprime $25$.
Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 6$.
Ejemplo 3
Entrada
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Salida
1
Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 6$.
Ejemplo 4
Entrada
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Salida
85
Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 4, 5, 6$.
Ejemplo 5
Entrada
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Salida
25
Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 5, 6$.