Đề bài
Vườn JOI có hình vuông được chia thành lưới gồm $N$ hàng theo chiều dọc và $N$ cột theo chiều ngang. Ô ở hàng thứ $i$ tính từ trên xuống ($1 \le i \le N$) và cột thứ $j$ tính từ trái sang ($1 \le j \le N$) được gọi là khu vực $(i, j)$.
Do vườn JOI không có thổ nhưỡng tốt lắm nên ở mỗi khu vực chỉ có thể trồng tối đa $1$ bông hoa thuộc $1$ màu cố định. Cụ thể, tại khu vực $(i, j)$, chỉ có thể trồng tối đa $1$ bông hoa màu đỏ khi $A_{i, j} =$ R, màu vàng khi $A_{i, j} =$ Y và màu xanh dương khi $A_{i, j} =$ B.
Tại đây, Giám đốc K — người quản lý khu vườn này — dự định trồng hoa theo quy trình sau để khu vườn trông thật đẹp khi chụp ảnh từ trên không:
- Chọn một số nguyên $r$ biểu thị kích thước. Tuy nhiên, phải thỏa mãn $0 \le r \le (N-1) \div 2$.
- Chọn một khu vực $(x, y)$ biểu thị tâm. Tuy nhiên, phải thỏa mãn $r+1 \le x \le N-r$ và $r+1 \le y \le N-r$.
- Chọn các màu $c_0, c_1, c_2, \dots, c_r$ lần lượt từ đỏ, vàng và xanh dương.
- Với mỗi khu vực $(x', y')$, trồng hoa dựa theo $d = |x'-x| + |y'-y|$ theo quy tắc sau, trong đó $|t|$ biểu thị giá trị tuyệt đối của $t$:
- Nếu $d \le r$, trồng một bông hoa có màu $c_d$ tại khu vực $(x', y')$.
- Nếu $d > r$, không trồng hoa tại khu vực $(x', y')$.
Cho biết kích thước của khu vườn và thông tin về màu hoa có thể trồng ở mỗi khu vực, hãy viết chương trình tìm số lượng hoa tối đa mà Giám đốc K có thể trồng.
Giới hạn
- $3 \le N \le 3\,500$.
- $A_{i, j}$ là một trong các ký tự
R,Y,B($1 \le i \le N, 1 \le j \le N$). - $N$ là số nguyên.
Subtask
- ($4$ điểm) $N = 3$.
- ($13$ điểm) $N \le 50$.
- ($17$ điểm) $N \le 800$.
- ($14$ điểm) Có nhiều nhất $5$ cặp $(i, j)$ ($1 \le i \le N, 1 \le j \le N$) thỏa mãn $A_{i, j} \neq$
R. - ($16$ điểm) Với mọi $(i, j)$ ($1 \le i \le N-1, 1 \le j \le N-1$), trong số $A_{i, j}$, $A_{i, j+1}$, $A_{i+1, j}$, $A_{i+1, j+1}$ có ít nhất $3$ ký tự
R. - ($36$ điểm) Không có giới hạn bổ sung.
Dữ liệu vào
Dữ liệu vào được cung cấp theo định dạng sau:
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}Kết quả
In ra trên $1$ dòng số lượng hoa tối đa mà Giám đốc K có thể trồng.
Ví dụ 1
Dữ liệu vào
3 RYR YBY BYY
Kết quả
5
Nếu đặt $r = 1$, $(x, y) = (2, 2)$, đồng thời chọn $c_0$ là xanh dương và $c_1$ là vàng, ta có thể trồng được $5$ bông hoa như hình dưới đây. Lưu ý rằng màu nền biểu thị màu hoa có thể trồng ở từng khu vực.
Vì không có cách nào trồng được từ $6$ bông hoa trở lên nên ta in ra $5$.
Ví dụ này thỏa mãn các giới hạn của Subtask $1, 2, 3, 6$.
Ví dụ 2
Dữ liệu vào
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
Kết quả
25
Nếu đặt $r = 3$, $(x, y) = (5, 6)$, đồng thời chọn $c_0$ là vàng, $c_1$ là vàng, $c_2$ là đỏ và $c_3$ là xanh dương, ta có thể trồng được $25$ bông hoa như hình dưới đây. Lưu ý rằng màu nền biểu thị màu hoa có thể trồng ở từng khu vực.
Vì không có cách nào trồng được từ $26$ bông hoa trở lên nên ta in ra $25$.
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 6$.
Ví dụ 3
Dữ liệu vào
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
Kết quả
1
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 6$.
Ví dụ 4
Dữ liệu vào
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
Kết quả
85
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 4, 5, 6$.
Ví dụ 5
Dữ liệu vào
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
Kết quả
25
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 5, 6$.