trang chủ / đề bài / icpcwf03_a

Xây cầu nối

Đề bài

Mô tả

Hội đồng thành phố New Altonville dự định xây một hệ thống cầu nối liền tất cả các toà nhà ở trung tâm thành phố, để mọi người có thể đi bộ từ toà nhà này sang toà nhà khác mà không cần ra ngoài trời. Bạn cần viết chương trình giúp tìm cách xây cầu tối ưu.

Thành phố New Altonville được chia thành một lưới các ô vuông. Mỗi toà nhà chiếm một tập liên thông gồm một hoặc nhiều ô. Hai ô có người chiếm mà chạm nhau ở góc được coi là thuộc cùng một toà nhà và không cần cầu. Cầu chỉ được xây trên các đường lưới (các cạnh của ô vuông). Mỗi cây cầu phải là một đoạn thẳng và phải nối đúng hai toà nhà.

Với một tập toà nhà cho trước, hãy tìm số cầu ít nhất cần xây để nối tất cả các toà nhà. Nếu không thể nối tất cả, hãy tìm cách làm cho số nhóm toà nhà không liên thông với nhau là ít nhất. Trong các cách có cùng số cầu, chọn cách có tổng độ dài các cầu nhỏ nhất, độ dài đo bằng số lần cạnh ô lưới. Hai cây cầu được phép cắt nhau, nhưng khi đó chúng được coi là nằm ở hai tầng khác nhau và không tạo đường đi từ cầu này sang cầu kia.

Hình dưới minh hoạ bốn thành phố. Thành phố 1 gồm năm toà nhà, có thể nối bằng bốn cây cầu với tổng độ dài 4. Ở thành phố 2 không xây được cây cầu nào, vì không có hai toà nhà nào cùng nằm trên một đường lưới. Ở thành phố 3 không cần cầu vì chỉ có một toà nhà. Ở thành phố 4, cách tốt nhất là xây một cây cầu dài 1 nối hai toà nhà, còn lại hai nhóm không liên thông (một nhóm gồm hai toà nhà và một nhóm gồm một toà nhà).

Dữ liệu vào

Dữ liệu gồm mô tả của nhiều thành phố hình chữ nhật. Mô tả của mỗi thành phố bắt đầu bằng một dòng chứa hai số nguyên r và c là kích thước của thành phố theo trục bắc nam và trục đông tây, tính bằng số cạnh ô lưới (1≤r≤50, 1≤c≤50). Tiếp theo là đúng r dòng, mỗi dòng gồm c ký tự # hoặc .. Mỗi ký tự ứng với một ô của lưới: # là ô có toà nhà chiếm, . là ô trống.

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

Dữ liệu ra

Với mỗi thành phố, in hai hoặc ba dòng như sau. Dòng đầu tiên là số thứ tự của thành phố: City k (bắt đầu từ k=1). Nếu thành phố có ít hơn hai toà nhà, dòng thứ hai là câu No bridges are needed.. Nếu thành phố có từ hai toà nhà trở lên nhưng không nối được hai toà nhà nào bằng cầu, dòng thứ hai là câu No bridges are possible.. Ngược lại, dòng thứ hai là N bridges of total length L, trong đó N là số cầu và L là tổng độ dài các cầu của cách xây tốt nhất (nếu N=1 thì dùng từ bridge thay cho bridges). Nếu cách xây để lại từ hai nhóm toà nhà không liên thông trở lên, in thêm dòng thứ ba chứa số nhóm không liên thông theo dạng G disconnected groups.

In một dòng trống giữa kết quả của hai thành phố liên tiếp. Định dạng phải giống ví dụ.

Ràng buộc

  • 1≤r,c≤50.
  • Mỗi file có không quá 100 thành phố.

Ví dụ

Input Output Giải thích
3 5
#...#
..#..
#...#
3 5
##...
.....
....#
3 5
#.###
#.#.#
###.#
3 5
#.#..
.....
....#
0 0
City 1
4 bridges of total length 4

City 2
No bridges are possible.
2 disconnected groups

City 3
No bridges are needed.

City 4
1 bridge of total length 1
2 disconnected groups
Bốn thành phố trong hình. Thành phố 1: mỗi toà nhà ở góc nối với toà nhà ở giữa bằng một cầu dài 1 chạy trên đường lưới giữa hàng 1 và hàng 2 (hoặc giữa hàng 2 và hàng 3), cầu bắt đầu ở góc của ô này và kết thúc ở góc của ô kia. Thành phố 3: mọi ô thuộc cùng một toà nhà.
2 3
...
...
1 1
#
4 6
#.....
.#..#.
......
.....#
3 7
#.....#
.......
...#...
1 8
#......#
0 0
City 1
No bridges are needed.

City 2
No bridges are needed.

City 3
2 bridges of total length 3

City 4
1 bridge of total length 5
2 disconnected groups

City 5
1 bridge of total length 6
Ví dụ tự thêm. Thành phố 1 không có toà nhà nào. Thành phố 3: hai ô ở góc trên bên trái chạm nhau ở góc nên là một toà nhà; nó nối với toà nhà ở hàng 2 cột 5 bằng một cầu dài 2 trên đường lưới giữa hàng 2 và hàng 3, toà nhà này nối với ô ở góc dưới bên phải bằng một cầu dài 1 trên đường lưới dọc giữa cột 5 và cột 6. Thành phố 4: toà nhà ở hàng 3 không chung đường lưới nào với hai toà nhà kia. Thành phố 5: cầu chạy trên đường lưới ở mép trên (hoặc mép dưới) của thành phố.

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