Kênh tưới
Đề bài
Mô tả
Joe, một cựu vô địch lập trình, cuối cùng cũng đã mua lại trang trại. Không, không, anh ấy vẫn sống khỏe mạnh; anh chỉ dùng số tiền khổng lồ giành được từ các cuộc thi lập trình để mua lại trang trại của tổ tiên. Anh hy vọng được nghỉ hưu và dành phần đời còn lại để chăm sóc bò (vì lý do nào đó, giờ anh tự coi mình là chuyên gia về bò).
Đáng buồn là ước mơ thôn quê giản dị của bác nông dân Joe không thành. Trang trại của anh nằm ở vùng khí hậu phía bắc lạnh giá, quá lạnh cho bò! Tệ hơn nữa, khí hậu ở đây khô hạn và không hợp để trồng trọt. Joe nhận ra anh sẽ phải xây dựng một hệ thống tưới tiêu cho cánh đồng. Hệ thống này dẫn một phần nước sông vào một con kênh dài, uốn lượn qua cánh đồng. Vì cây trồng gần kênh nhất sẽ tươi tốt, kênh càng dài càng tốt.
Cánh đồng của anh là một dải đất hình chữ nhật dài, chia thành các ô vuông đơn vị. Mỗi ô hoặc là đất, ký hiệu ., hoặc là một tảng đá không thể di chuyển, ký hiệu #. Kênh tưới rộng một ô, đi vào cánh đồng ở ô góc trên bên trái và đi ra ở ô góc dưới bên phải. Tất nhiên kênh không thể đi qua đá. Điều quan trọng là kênh không bao giờ được chạm vào chính nó, kể cả chạm ở góc (nếu không nước sẽ thấm qua và đi tắt). Hình 3 và Hình 4 là các ví dụ về kênh chạm vào chính nó (các ô kênh được tô màu, chỗ chạm tô đỏ).
Hình 3:
grid ..... ..... ..... ..... ..... ..... path orange 1,1 2,1 3,1 3,2 3,3 2,3 1,3 1,4 1,5 2,5 3,5 4,5 4,4 5,4 6,4 6,5 highlight red 3,3 4,4
Hình 4:
grid .... .... .... .... .... .... path orange 1,1 2,1 2,2 2,3 2,4 3,4 3,3 4,3 5,3 6,3 6,4 highlight red 2,3 2,4 3,3 3,4
Nói chính xác: kênh là một dãy các ô đất đôi một khác nhau, với là ô góc trên bên trái, là ô góc dưới bên phải, và hai ô liên tiếp chung một cạnh. Kênh không chạm vào chính nó nghĩa là: hai ô với có chung cạnh hoặc chung đỉnh thì phải có , hoặc và hai ô chéo nhau (chỗ kênh rẽ). Độ dài của kênh là số ô .
Joe đã qua thời đỉnh cao lập trình từ lâu. Anh có một lời giải đơn giản nhưng hóa ra chạy quá lâu. Bạn hãy giúp anh tìm cách đặt con kênh tối ưu.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa là số hàng của cánh đồng và là số cột. dòng tiếp theo, mỗi dòng là một xâu độ dài mô tả cánh đồng.
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test theo dạng Case i:. Trên dòng tiếp theo, in cánh đồng với con kênh dài nhất có thể đặt được theo các quy tắc trên, dùng ký tự C cho các ô của kênh. Dữ liệu bảo đảm lời giải luôn tồn tại và duy nhất. In một dòng trống sau kết quả của mỗi bộ test. Làm theo đúng định dạng của ví dụ.
Ràng buộc
- , .
- Mỗi xâu chỉ gồm các ký tự
.và#. - Con kênh dài nhất tồn tại và duy nhất.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 .#. ... .#. 6 7 ....... ....... ....... ....#.. ....... .#..... 0 0 |
Case 1: C#. CCC .#C Case 2: CCCCCCC ......C CCCCCCC C...#.. CCC.CCC .#CCC.C |
Ví dụ của đề gốc. Ở bộ test 1, kênh duy nhất có độ dài . Ở bộ test 2, kênh dài nhất có ô; ở chỗ rẽ, hai ô cách nhau hai bước được phép chéo nhau. |
| 5 5 ..... .#... ...#. .#... ..... 5 4 .... ..#. .... .#.. .... 2 5 ..... ...#. 0 0 |
Case 1: C.CCC C#C.C C.C#C C#C.C CCC.C Case 2: CCCC ..#C CCCC C#.. CCCC Case 3: C.CCC CCC#C |
Các kênh dài nhất có độ dài , và . |
Bình luận