Énoncé du problème
Le jardin JOI a la forme d'un carré divisé en une grille de $N$ lignes verticalement et $N$ colonnes horizontalement. La case située à la $i$-ème ligne depuis le haut ($1 \le i \le N$) et à la $j$-ème colonne depuis la gauche ($1 \le j \le N$) est appelée la parcelle $(i, j)$.
Comme le jardin JOI n'est pas doté d'un très bon sol, dans chaque parcelle, on ne peut planter au maximum qu'$1$ seule fleur d'$1$ couleur spécifique. Plus précisément, dans la parcelle $(i, j)$, on ne peut planter au maximum qu'$1$ fleur de couleur rouge lorsque $A_{i, j} =$ R, jaune lorsque $A_{i, j} =$ Y et bleue lorsque $A_{i, j} =$ B.
Le directeur K, qui gère ce jardin, souhaite planter des fleurs selon la procédure suivante afin que le rendu soit joli sur une photographie aérienne :
- Choisir un entier $r$ représentant la taille. Il doit vérifier $0 \le r \le (N-1) \div 2$.
- Choisir une parcelle $(x, y)$ représentant le centre. Elle doit vérifier $r+1 \le x \le N-r$ et $r+1 \le y \le N-r$.
- Choisir et fixer des couleurs $c_0, c_1, c_2, \dots, c_r$ chacune parmi le rouge, le jaune et le bleu.
- Pour chaque parcelle $(x', y')$, planter une fleur en fonction de $d = |x'-x| + |y'-y|$ selon les règles suivantes, où $|t|$ désigne la valeur absolue de $t$ :
- Si $d \le r$, planter une fleur de couleur $c_d$ dans la parcelle $(x', y')$.
- Si $d > r$, ne pas planter de fleur dans la parcelle $(x', y')$.
Étant donné la taille du jardin et les informations sur la couleur des fleurs pouvant être plantées dans chaque parcelle, écrivez un programme pour déterminer le nombre maximal de fleurs que le directeur K peut planter.
Contraintes
- $3 \le N \le 3\,500$.
- $A_{i, j}$ est l'un des caractères
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ est un entier.
Sous-tâches
- ($4$ points) $N = 3$.
- ($13$ points) $N \le 50$.
- ($17$ points) $N \le 800$.
- ($14$ points) Il y a au plus $5$ couples $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) vérifiant $A_{i, j} \neq$
R. - ($16$ points) Pour tout $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), parmi $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$, il y a au moins $3$ occurrences de
R. - ($36$ points) Aucune contrainte supplémentaire.
Entrée
L'entrée est donnée sous le format suivant :
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}Sortie
Affichez sur $1$ ligne le nombre maximal de fleurs que le directeur K peut planter.
Exemple 1
Entrée
3 RYR YBY BYY
Sortie
5
Si l'on pose $r = 1$ et $(x, y) = (2, 2)$, et que l'on choisit le bleu comme $c_0$ et le jaune comme $c_1$, on peut planter $5$ fleurs comme illustré ci-dessous. Ici, la couleur de fond indique la couleur de la fleur qui peut être plantée dans chaque parcelle.
Comme il n'existe aucun moyen de planter $6$ fleurs ou plus, on affiche $5$.
Cet exemple d'entrée vérifie les contraintes des sous-tâches $1, 2, 3, 6$.
Exemple 2
Entrée
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Sortie
25
Si l'on pose $r = 3$ et $(x, y) = (5, 6)$, et que l'on choisit le jaune comme $c_0$, le jaune comme $c_1$, le rouge comme $c_2$ et le bleu comme $c_3$, on peut planter $25$ fleurs comme illustré ci-dessous. Ici, la couleur de fond indique la couleur de la fleur qui peut être plantée dans chaque parcelle.
Comme il n'existe aucun moyen de planter $26$ fleurs ou plus, on affiche $25$.
Cet exemple d'entrée vérifie les contraintes des sous-tâches $2, 3, 6$.
Exemple 3
Entrée
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Sortie
1
Cet exemple d'entrée vérifie les contraintes des sous-tâches $2, 3, 6$.
Exemple 4
Entrée
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Sortie
85
Cet exemple d'entrée vérifie les contraintes des sous-tâches $2, 3, 4, 5, 6$.
Exemple 5
Entrée
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Sortie
25
Cet exemple d'entrée vérifie les contraintes des sous-tâches $2, 3, 5, 6$.