trang chủ / đề bài / icpcwf10_e

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 p1,p2,…,pk đôi một khác nhau, với p1 là ô góc trên bên trái, pk 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 ô pi,pj với i<j có chung cạnh hoặc chung đỉnh thì phải có j=i+1, hoặc j=i+2 và hai ô chéo nhau (chỗ kênh rẽ). Độ dài của kênh là số ô k.

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 r là số hàng của cánh đồng và c là số cột. r dòng tiếp theo, mỗi dòng là một xâu độ dài c mô tả cánh đồng.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

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 r 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

  • 2≤r≤20, 2≤c≤9.
  • 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 5. Ở bộ test 2, kênh dài nhất có 26 ô; ở 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 17, 14 và 8.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0