4. JOI 2024 - Garden 2
Vườn JOI có dạng hình vuông, được chia thành \(N\) hàng và \(N\) cột ô vuông. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang được gọi là ô \((i,j)\) (\(1 \le i,j \le N\)).
Đất trong vườn không tốt lắm, nên mỗi ô chỉ có thể trồng tối đa một bông hoa thuộc một màu nhất định. Cụ thể, ô \((i,j)\) chỉ có thể trồng hoa đỏ nếu \(A_{i,j}\) là R, hoa vàng nếu là Y, và hoa xanh dương nếu là B.
Để khu vườn đẹp hơn khi chụp ảnh từ trên không, ông K, người quản lý khu vườn, dự định trồng hoa theo quy trình sau:
- Chọn số nguyên \(r\) biểu diễn kích thước, thỏa mãn \(0 \le r \le (N-1)/2\).
- Chọn ô trung tâm \((x,y)\), thỏa mãn \(r+1 \le x \le N-r\) và \(r+1 \le y \le N-r\).
- Với mỗi \(d\) từ \(0\) đến \(r\), chọn màu \(c_d\) là đỏ, vàng hoặc xanh dương.
- Với mỗi ô \((x',y')\), đặt \(d = |x'-x| + |y'-y|\), trong đó \(|t|\) là giá trị tuyệt đối của \(t\). Nếu \(d \le r\), trồng một bông hoa màu \(c_d\) tại ô đó; nếu \(d > r\), không trồng hoa tại ô đó.
Việc trồng hoa phải phù hợp với màu hoa mà từng ô cho phép. Cho kích thước khu vườn và màu hoa có thể trồng ở mỗi ô, hãy viết chương trình tìm số bông hoa nhiều nhất mà ông K có thể trồng.
Dữ liệu vào
Dòng thứ nhất chứa số nguyên \(N\).
Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa xâu gồm \(N\) ký tự \(A_{i,1}A_{i,2}\ldots A_{i,N}\), không có dấu cách giữa các ký tự.
Dữ liệu ra
In ra trên một dòng số bông hoa nhiều nhất mà ông K có thể trồng.
Ràng buộc
- \(3 \le N \le 3500\).
- \(A_{i,j}\) là
R,YhoặcBvới mọi \(1 \le i \le N\), \(1 \le j \le N\). - \(N\) là số nguyên.
Phân nhóm
Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.
- (4 điểm) \(N = 3\).
- (13 điểm) \(N \le 50\).
- (17 điểm) \(N \le 800\).
- (14 điểm) Có không quá \(5\) ô \((i,j)\) với \(1 \le i \le N\), \(1 \le j \le N\) mà \(A_{i,j}\) khác
R. - (16 điểm) Với mọi \(1 \le i \le N-1\), \(1 \le j \le N-1\), có ít nhất \(3\) giá trị bằng
Rtrong bốn giá trị \(A_{i,j}\), \(A_{i,j+1}\), \(A_{i+1,j}\), \(A_{i+1,j+1}\). - (36 điểm) Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
3
RYR
YBY
BYYOutput
5Giải thích
Chọn \(r=1\), \((x,y)=(2,2)\), \(c_0\) là xanh dương và \(c_1\) là vàng thì có thể trồng \(5\) bông hoa như hình dưới đây. Màu nền của mỗi ô biểu diễn màu hoa có thể trồng tại ô đó. Trong hình, 黄 chỉ hoa vàng và 青 chỉ hoa xanh dương.
Không có cách trồng từ \(6\) bông hoa trở lên, nên in ra \(5\).
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 6\).
Ví dụ 2
Input
9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRYOutput
25Giải thích
Chọn \(r=3\), \((x,y)=(5,6)\), \(c_0\) và \(c_1\) là vàng, \(c_2\) là đỏ, \(c_3\) là xanh dương thì có thể trồng \(25\) bông hoa như hình dưới đây. Màu nền của mỗi ô biểu diễn màu hoa có thể trồng tại ô đó. Trong hình, 赤 chỉ hoa đỏ, 黄 chỉ hoa vàng và 青 chỉ hoa xanh dương.
Không có cách trồng từ \(26\) bông hoa trở lên, nên in ra \(25\).
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 6\).
Ví dụ 3
Input
6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRBOutput
1Giải thích
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 6\).
Ví dụ 4
Input
20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRROutput
85Giải thích
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 4, 5, 6\).
Ví dụ 5
Input
10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRROutput
25Giải thích
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 5, 6\).
Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
