Verkefnalýsing

JOI-garðurinn er ferhyrningslaga svæði sem skipt er í grind með $N$ röðum lóðrétt og $N$ dálkum lárétt. Reiturinn í $i$-tu röðinni að ofan ($1 \le i \le N$) og $j$-ta dálkinum frá vinstri ($1 \le j \le N$) kallast reitur $(i, j)$.

Þar sem jarðvegurinn í JOI-garðinum er ekki mjög frjósamur er í mesta lagi hægt að gróðursetja $1$ blóm af $1$ tilteknum lit í hverjum reit. Nánar tiltekið er í reit $(i, j)$ í mesta lagi hægt að gróðursetja $1$ rautt blóm þegar $A_{i, j} =$ R, gult þegar $A_{i, j} =$ Y og blátt þegar $A_{i, j} =$ B.

Framkvæmdastjórinn K, sem sér um þennan garð, ætlar að gróðursetja blóm samkvæmt eftirfarandi ferli til þess að garðurinn líti vel út á loftmynd:

1. Ákveða heiltölu $r$ sem táknar stærðina. Hér verður $0 \le r \le (N-1) \div 2$ að gilda.
2. Ákveða reit $(x, y)$ sem táknar miðjuna. Hér verður $r+1 \le x \le N-r$ og $r+1 \le y \le N-r$ að gilda.
3. Velja og ákveða litina $c_0, c_1, c_2, \dots, c_r$, hvern um sig úr rauðum, gulum og bláum.
4. Fyrir hvern reit $(x', y')$ skal gróðursetja blóm út frá $d = |x'-x| + |y'-y|$ samkvæmt eftirfarandi reglum, þar sem $|t|$ táknar tölugildi $t$:
   • Ef $d \le r$, gróðursetjið blóm af lit $c_d$ í reit $(x', y')$.
   • Ef $d > r$, gróðursetjið ekkert blóm í reit $(x', y')$.

Þegar stærð garðsins og upplýsingar um liti blómanna sem hægt er að gróðursetja í hverjum reit eru gefnar, skrifið forrit til að finna mesta fjölda blóma sem framkvæmdastjórinn K getur gróðursett.

Skorður

• $3 \le N \le 3\,500$.
• $A_{i, j}$ er annaðhvort R, Y eða B ($1 \le i \le N, 1 \le j \le N$).
• $N$ er heiltala.

Undirverkefni

1. ($4$ stig) $N = 3$.
2. ($13$ stig) $N \le 50$.
3. ($17$ stig) $N \le 800$.
4. ($14$ stig) Það eru í mesta lagi $5$ pör $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) sem uppfylla $A_{i, j} \neq$ R.
5. ($16$ stig) Fyrir sérhvert $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$) eru að minnsta kosti $3$ tilvik af R meðal $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$.
6. ($36$ stig) Engar viðbótarskorður.

Inntak

Inntakið er gefið á eftirfarandi sniði:

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}

Úttak

Prentið í $1$ línu mesta fjölda blóma sem framkvæmdastjórinn K getur gróðursett.

Dæmi 1

Inntak

3
RYR
YBY
BYY

Úttak

5

Ef við setjum $r = 1$ og $(x, y) = (2, 2)$, og veljum bláan sem $c_0$ og gulan sem $c_1$, getum við gróðursett $5$ blóm eins og sýnt er á myndinni hér að neðan. Hér sýnir bakgrunnsliturinn litinn á blóminu sem hægt er að gróðursetja í hverjum reit.

Þar sem engin leið er til að gróðursetja $6$ eða fleiri blóm er prentað $5$.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $1, 2, 3, 6$.

Dæmi 2

Inntak

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

Úttak

25

Ef við setjum $r = 3$ og $(x, y) = (5, 6)$, og veljum gulan sem $c_0$, gulan sem $c_1$, rauðan sem $c_2$ og bláan sem $c_3$, getum við gróðursett $25$ blóm eins og sýnt er á myndinni hér að neðan. Hér sýnir bakgrunnsliturinn litinn á blóminu sem hægt er að gróðursetja í hverjum reit.

Þar sem engin leið er til að gróðursetja $26$ eða fleiri blóm er prentað $25$.

Þetta inntaksdæmi uppfyllir skorður undirverkefna $2, 3, 6$.

Dæmi 3

Inntak

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

Úttak

1

Þetta inntaksdæmi uppfyllir skorður undirverkefna $2, 3, 6$.

Dæmi 4

Inntak

20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR

Úttak

85

Þetta inntaksdæmi uppfyllir skorður undirverkefna $2, 3, 4, 5, 6$.

Dæmi 5

Inntak

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

Úttak

25

Þetta inntaksdæmi uppfyllir skorður undirverkefna $2, 3, 5, 6$.