Món quà
Đề bài
Mô tả
Sắp đến sinh nhật Khánh Đan, Scratch quyết định tự tay làm một món đồ để tặng. Cụ thể, Scratch tự làm một khối gỗ lớn kích thước (ghép từ khối đơn vị). Tuy nhiên, do Scratch còn thiếu kinh nghiệm, một số khối đơn vị trong khối lớn bị lỗi (nứt, rỗng bên trong, ...). Scratch không thể tặng một món quà như vậy.
Vì thế, Scratch dự định đục ra từ khối lớn một khối con (khối hộp chữ nhật được đục ra phải có hai cạnh kề nhau bằng nhau). Dĩ nhiên, khối con này không được chứa khối đơn vị lỗi nào.
Scratch muốn chọn phương án có giá trị lớn nhất trong tất cả các phương án có thể. Nhưng chỉ riêng việc kiểm tra xem phần nào của khối bị lỗi đã khiến Scratch kiệt sức. Là bạn tốt của Scratch, bạn hãy giúp cậu ấy nhé!
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên dương (), cách nhau bởi dấu cách.
Mỗi dòng trong dòng tiếp theo chứa ký tự, mỗi ký tự là P (khối lỗi) hoặc N (khối bình thường), cho biết khối đơn vị tương ứng bị lỗi hay còn nguyên vẹn. Cụ thể, ký tự thứ trên dòng thứ trong dòng này mô tả tình trạng của khối đơn vị ở tọa độ (, , ).
Dữ liệu ra
In ra một số nguyên là giá trị lớn nhất. Khối con có thể nằm theo bất kỳ hướng nào (cặp cạnh bằng nhau có thể song song với bất kỳ hai trục tọa độ nào); nếu mọi khối đơn vị đều lỗi, in ra .
Ràng buộc
- .
- Mỗi ký tự là
PhoặcN.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 5 NNNNP NPNPN PNPPN NNNNN NNNNN NNNNN NNNNP NNPPN NNPPN PNNNN NNNNN NNPNN |
24 | Ví dụ của đề gốc. Khối con gồm các ô có , , không chứa khối lỗi, cho , , . |
| 2 3 4 NNNN NNNN NNNP NNNN PNNN NNNN |
24 | Ví dụ bổ sung (không có trong đề gốc). Khối con gồm các ô có , , không chứa khối lỗi (, ). Khối , , (cặp cạnh bằng nhau theo trục và ) cũng cho . |
Bình luận