Testo del problema
Il giardino JOI ha la forma di un quadrato diviso in una griglia di $N$ righe verticalmente e $N$ colonne orizzontalmente. La cella nella $i$-esima riga dall'alto ($1 \le i \le N$) e nella $j$-esima colonna da sinistra ($1 \le j \le N$) è chiamata settore $(i, j)$.
Poiché il giardino JOI non gode di un terreno molto fertile, in ciascun settore è possibile piantare al massimo $1$ fiore di $1$ colore specifico. Nello specifico, nel settore $(i, j)$ è possibile piantare al massimo $1$ fiore di colore rosso quando $A_{i, j} =$ R, giallo quando $A_{i, j} =$ Y e blu quando $A_{i, j} =$ B.
Il direttore K, gestore di questo giardino, intende piantare dei fiori seguendo la procedura seguente affinché il giardino abbia un bel aspetto nelle fotografie aeree:
- Scegliere un intero $r$ che rappresenta la dimensione. Deve essere soddisfatta la condizione $0 \le r \le (N-1) \div 2$.
- Scegliere un settore $(x, y)$ che rappresenta il centro. Devono essere soddisfatte le condizioni $r+1 \le x \le N-r$ e $r+1 \le y \le N-r$.
- Scegliere e fissare i colori $c_0, c_1, c_2, \dots, c_r$, ciascuno tra rosso, giallo e blu.
- Per ciascun settore $(x', y')$, piantare un fiore in base a $d = |x'-x| + |y'-y|$ secondo le seguenti regole, dove $|t|$ indica il valore assoluto di $t$:
- Se $d \le r$, piantare un fiore di colore $c_d$ nel settore $(x', y')$.
- Se $d > r$, non piantare alcun fiore nel settore $(x', y')$.
Date le dimensioni del giardino e le informazioni sui colori dei fiori che possono essere piantati in ciascun settore, scrivi un programma per trovare il numero massimo di fiori che il direttore K può piantare.
Vincoli
- $3 \le N \le 3\,500$.
- $A_{i, j}$ è uno tra
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ è un numero intero.
Sottoproblemi
- ($4$ punti) $N = 3$.
- ($13$ punti) $N \le 50$.
- ($17$ punti) $N \le 800$.
- ($14$ punti) Ci sono al massimo $5$ coppie $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) che soddisfano $A_{i, j} \neq$
R. - ($16$ punti) Per ogni $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), tra $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ ci sono almeno $3$ occorrenze di
R. - ($36$ punti) Nessun vincolo aggiuntivo.
Input
L'input è fornito nel seguente 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}Output
Stampa in $1$ riga il numero massimo di fiori che il direttore K può piantare.
Esempio 1
Input
3 RYR YBY BYY
Output
5
Se poniamo $r = 1$ e $(x, y) = (2, 2)$, e scegliamo il blu come $c_0$ e il giallo come $c_1$, possiamo piantare $5$ fiori come mostrato nella figura sottostante. Qui il colore di sfondo indica il colore del fiore che può essere piantato in ciascun settore.
Poiché non c'è modo di piantare $6$ o più fiori, si stampa $5$.
Questo esempio di input soddisfa i vincoli dei sottoproblemi $1, 2, 3, 6$.
Esempio 2
Input
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Output
25
Se poniamo $r = 3$ e $(x, y) = (5, 6)$, e scegliamo il giallo come $c_0$, il giallo come $c_1$, il rosso come $c_2$ e il blu come $c_3$, possiamo piantare $25$ fiori come mostrato nella figura sottostante. Qui il colore di sfondo indica il colore del fiore che può essere piantato in ciascun settore.
Poiché non c'è modo di piantare $26$ o più fiori, si stampa $25$.
Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 6$.
Esempio 3
Input
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Output
1
Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 6$.
Esempio 4
Input
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Output
85
Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 4, 5, 6$.
Esempio 5
Input
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Output
25
Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 5, 6$.