Problembeskrivning
JOI-trädgården har formen av en kvadrat uppdelad i ett rutnät med $N$ rader vertikalt och $N$ kolumner horisontellt. Rutan på den $i$-te raden uppifrån ($1 \le i \le N$) och den $j$-te kolumnen från vänster ($1 \le j \le N$) kallas sektion $(i, j)$.
Eftersom JOI-trädgården inte har särskilt bra jord kan man i varje sektion plantera högst $1$ blomma av $1$ specifik färg. Mer specifikt kan man i sektion $(i, j)$ plantera högst $1$ röd blomma när $A_{i, j} =$ R, gul när $A_{i, j} =$ Y och blå när $A_{i, j} =$ B.
Här tänker direktör K, som förvaltar denna trädgård, plantera blommor enligt följande procedur för att det ska se fint ut när man tar ett flygfoto:
- Bestäm ett heltal $r$ som representerar storleken. Här måste $0 \le r \le (N-1) \div 2$ vara uppfyllt.
- Bestäm en sektion $(x, y)$ som representerar centrum. Här måste $r+1 \le x \le N-r$ och $r+1 \le y \le N-r$ vara uppfyllda.
- Välj och bestäm färgerna $c_0, c_1, c_2, \dots, c_r$, var och en bland röd, gul och blå.
- För varje sektion $(x', y')$, plantera en blomma beroende på $d = |x'-x| + |y'-y|$ enligt följande regler, där $|t|$ betecknar absolutbeloppet av $t$:
- Om $d \le r$, plantera en blomma av färgen $c_d$ i sektion $(x', y')$.
- Om $d > r$, plantera ingen blomma i sektion $(x', y')$.
Givet trädgårdens storlek och information om vilka blomfärger som kan planteras i varje sektion, skriv ett program som beräknar det maximala antalet blommor som direktör K kan plantera.
Begränsningar
- $3 \le N \le 3\,500$.
- $A_{i, j}$ är något av
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ är ett heltal.
Deluppgifter
- ($4$ poäng) $N = 3$.
- ($13$ poäng) $N \le 50$.
- ($17$ poäng) $N \le 800$.
- ($14$ poäng) Det finns högst $5$ par $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) som uppfyller $A_{i, j} \neq$
R. - ($16$ poäng) För varje $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) finns det minst $3$ stycken
Rbland $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$. - ($36$ poäng) Inga ytterligare begränsningar.
Indata
Indata ges i följande format:
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}Utdata
Skriv ut det maximala antalet blommor som direktör K kan plantera på $1$ rad.
Exempel 1
Indata
3 RYR YBY BYY
Utdata
5
Om vi sätter $r = 1$ och $(x, y) = (2, 2)$, samt väljer blå som $c_0$ och gul som $c_1$, kan vi plantera $5$ blommor som i figuren nedan. Här visar bakgrundsfärgen vilken färg på blomman som kan planteras i respektive sektion.
Eftersom det inte finns något sätt att plantera $6$ eller fler blommor skrivs $5$ ut.
Detta indataexempel uppfyller begränsningarna för deluppgift $1, 2, 3, 6$.
Exempel 2
Indata
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Utdata
25
Om vi sätter $r = 3$ och $(x, y) = (5, 6)$, samt väljer gul som $c_0$, gul som $c_1$, röd som $c_2$ och blå som $c_3$, kan vi plantera $25$ blommor som i figuren nedan. Här visar bakgrundsfärgen vilken färg på blomman som kan planteras i respektive sektion.
Eftersom det inte finns något sätt att plantera $26$ eller fler blommor skrivs $25$ ut.
Detta indataexempel uppfyller begränsningarna för deluppgift $2, 3, 6$.
Exempel 3
Indata
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Utdata
1
Detta indataexempel uppfyller begränsningarna för deluppgift $2, 3, 6$.
Exempel 4
Indata
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Utdata
85
Detta indataexempel uppfyller begränsningarna för deluppgift $2, 3, 4, 5, 6$.
Exempel 5
Indata
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Utdata
25
Detta indataexempel uppfyller begränsningarna för deluppgift $2, 3, 5, 6$.