نص المسألة
تأخذ حديقة 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$، تُزرع زهرة من اللون $c_d$ في القطعة $(x', y')$.
- إذا كان $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$)، يوجد على الأقل $3$ من الحرف
Rمن بين $A_{i, j}$ و $A_{i, j+1}$ و $A_{i+1, j}$ و $A_{i+1, j+1}$. - ($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$.