תיאור הבעיה
גן JOI הוא בצורת ריבוע המחולק לרשת של $N$ שורות לאורך ו-$N$ עמודות לרוחב. התא בשורה ה-$i$ מלמעלה ($1 \le i \le N$) ובעמודה ה-$j$ משמאל ($1 \le j \le N$) נקרא חלקה $(i, j)$.
מכיוון שגן JOI אינו מבורך באדמה פורייה במיוחד, בכל חלקה ניתן לשתול לכל היותר פרח $1$ מצבע מסוים $1$. באופן ספציפי, בחלקה $(i, j)$ ניתן לשתול לכל היותר פרח $1$ בצבע אדום כאשר $A_{i, j} =$ R, צהוב כאשר $A_{i, j} =$ Y, וכחול כאשר $A_{i, j} =$ B.
כאן, המנהל K, המנהל של הגן הזה, מתכוון לשתול פרחים לפי ההליך הבא כדי שהגן ייראה יפה בצילום אווירי:
- לקבוע מספר שלם $r$ המייצג את הגודל. עליו לקיים $0 \le r \le (N-1) \div 2$.
- לקבוע חלקה $(x, y)$ המייצגת את המרכז. עליה לקיים $r+1 \le x \le N-r$ וכן $r+1 \le y \le N-r$.
- לבחור ולקבוע צבעים $c_0, c_1, c_2, \dots, c_r$ כל אחד מתוך אדום, צהוב וכחול.
- עבור כל חלקה $(x', y')$, לשתול פרח בהתאם ל-$d = |x'-x| + |y'-y|$ לפי הכללים הבאים, כאשר $|t|$ מייצג את הערך המוחלט של $t$:
- אם $d \le r$, שותלים בחלקה $(x', y')$ פרח בצבע $c_d$.
- אם $d > r$, לא שותלים פרח בחלקה $(x', y')$.
בהינתן גודל הגן ומידע על צבעי הפרחים שניתן לשתול בכל חלקה, כתבו תוכנית המוצאת את המספר המרבי של פרחים שהמנהל K יכול לשתול.
מגבלות
- $3 \le N \le 3\,500$.
- $A_{i, j}$ הוא אחד מבין
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ הוא מספר שלם.
תתי-משימות
- ($4$ נקודות) $N = 3$.
- ($13$ נקודות) $N \le 50$.
- ($17$ נקודות) $N \le 800$.
- ($14$ נקודות) יש לכל היותר $5$ זוגות $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) המקיימים $A_{i, j} \neq$
R. - ($16$ נקודות) עבור כל $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), מתוך $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ ישנם לפחות $3$ מופעים של
R. - ($36$ נקודות) אין מגבלות נוספות.
קלט
הקלט ניתן בפורמט הבא:
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}פלט
הדפיסו בשורה $1$ את המספר המרבי של פרחים שהמנהל K יכול לשתול.
דוגמה 1
קלט
3 RYR YBY BYY
פלט
5
אם נקבע $r = 1$ ו-$(x, y) = (2, 2)$, ונבחר כחול בתור $c_0$ וצהוב בתור $c_1$, נוכל לשתול $5$ פרחים כפי שמוצג באיור למטה. כאן, צבע הרקע מציין את צבע הפרח שניתן לשתול בכל חלקה.
מכיוון שאין דרך לשתול $6$ פרחים או יותר, מדפיסים $5$.
קלט לדוגמה זה מקיים את המגבלות של תתי-משימות $1, 2, 3, 6$.
דוגמה 2
קלט
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
פלט
25
אם נקבע $r = 3$ ו-$(x, y) = (5, 6)$, ונבחר צהוב בתור $c_0$, צהוב בתור $c_1$, אדום בתור $c_2$, וכחול בתור $c_3$, נוכל לשתול $25$ פרחים כפי שמוצג באיור למטה. כאן, צבע הרקע מציין את צבע הפרח שניתן לשתול בכל חלקה.
מכיוון שאין דרך לשתול $26$ פרחים או יותר, מדפיסים $25$.
קלט לדוגמה זה מקיים את המגבלות של תתי-משימות $2, 3, 6$.
דוגמה 3
קלט
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
פלט
1
קלט לדוגמה זה מקיים את המגבלות של תתי-משימות $2, 3, 6$.
דוגמה 4
קלט
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
פלט
85
קלט לדוגמה זה מקיים את המגבלות של תתי-משימות $2, 3, 4, 5, 6$.
דוגמה 5
קלט
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
פלט
25
קלט לדוגמה זה מקיים את המגבלות של תתי-משימות $2, 3, 5, 6$.