Problembeskrivelse
JOI-hagen har form som et kvadrat delt inn i et rutenett med $N$ rader vertikalt og $N$ kolonner horisontalt. Ruten i den $i$-te raden ovenfra ($1 \le i \le N$) og den $j$-te kolonnen fra venstre ($1 \le j \le N$) kalles seksjon $(i, j)$.
Siden JOI-hagen ikke har særlig god jord, kan man i hver seksjon plante maksimalt $1$ blomst av $1$ bestemt farge. Mer spesifikt kan man i seksjon $(i, j)$ plante maksimalt $1$ rød blomst når $A_{i, j} =$ R, gul når $A_{i, j} =$ Y og blå når $A_{i, j} =$ B.
Her ønsker direktør K, som bestyrer denne hagen, å plante blomster etter følgende prosedyre for at det skal se pent ut når man tar flyfoto:
- Bestem et heltall $r$ som representerer størrelsen. Her må $0 \le r \le (N-1) \div 2$ være oppfylt.
- Bestem en seksjon $(x, y)$ som representerer sentrum. Her må $r+1 \le x \le N-r$ og $r+1 \le y \le N-r$ være oppfylt.
- Velg og bestem fargene $c_0, c_1, c_2, \dots, c_r$, hver av dem blant rød, gul og blå.
- For hver seksjon $(x', y')$, plant en blomst avhengig av $d = |x'-x| + |y'-y|$ etter følgende regler, der $|t|$ betegner absoluttverdien til $t$:
- Hvis $d \le r$, plant en blomst med farge $c_d$ i seksjon $(x', y')$.
- Hvis $d > r$, ikke plant noen blomst i seksjon $(x', y')$.
Gitt størrelsen på hagen og informasjon om hvilke blomsterfarger som kan plantes i hver seksjon, skriv et program som finner det maksimale antallet blomster direktør K kan plante.
Begrensninger
- $3 \le N \le 3\,500$.
- $A_{i, j}$ er en av
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ er et heltall.
Deloppgaver
- ($4$ poeng) $N = 3$.
- ($13$ poeng) $N \le 50$.
- ($17$ poeng) $N \le 800$.
- ($14$ poeng) Det er høyst $5$ par $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) som oppfyller $A_{i, j} \neq$
R. - ($16$ poeng) For enhver $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) finnes det minst $3$ forekomster av
Rblant $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$. - ($36$ poeng) Ingen ytterligere begrensninger.
Inndata
Inndataene gis i følgende 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 maksimale antallet blomster direktør K kan plante på $1$ linje.
Eksempel 1
Inndata
3 RYR YBY BYY
Utdata
5
Hvis vi setter $r = 1$ og $(x, y) = (2, 2)$, og velger blå som $c_0$ og gul som $c_1$, kan vi plante $5$ blomster som vist i figuren nedenfor. Her viser bakgrunnsfargen hvilken blomsterfarge som kan plantes i hver seksjon.
Siden det ikke finnes noen måte å plante $6$ eller flere blomster på, skrives $5$ ut.
Dette inndataeksempelet oppfyller begrensningene i deloppgave $1, 2, 3, 6$.
Eksempel 2
Inndata
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Utdata
25
Hvis vi setter $r = 3$ og $(x, y) = (5, 6)$, og velger gul som $c_0$, gul som $c_1$, rød som $c_2$ og blå som $c_3$, kan vi plante $25$ blomster som vist i figuren nedenfor. Her viser bakgrunnsfargen hvilken blomsterfarge som kan plantes i hver seksjon.
Siden det ikke finnes noen måte å plante $26$ eller flere blomster på, skrives $25$ ut.
Dette inndataeksempelet oppfyller begrensningene i deloppgave $2, 3, 6$.
Eksempel 3
Inndata
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Utdata
1
Dette inndataeksempelet oppfyller begrensningene i deloppgave $2, 3, 6$.
Eksempel 4
Inndata
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Utdata
85
Dette inndataeksempelet oppfyller begrensningene i deloppgave $2, 3, 4, 5, 6$.
Eksempel 5
Inndata
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Utdata
25
Dette inndataeksempelet oppfyller begrensningene i deloppgave $2, 3, 5, 6$.