Nhà vua muốn xây dựng các cây cầu và ông muốn chúng được hoàn thành càng nhanh càng tốt. Nhà vua sở hữu một lưới đất kích thước \(N \times M\), với mỗi ô được ngăn cách với các ô liền kề bởi một con sông chạy giữa chúng. Ông muốn bạn tính toán xem cần bao nhiêu giờ công (man-hours) để xây dựng đủ số cầu nhằm kết nối tất cả các hòn đảo. Một số ô thực chất là hồ nước và không cần phải xây cầu đến đó.

Một số hòn đảo là rừng, nơi có nguồn gỗ dồi dào. Nằm ở góc trên cùng bên trái là căn cứ trung tâm, nơi này luôn là một khu rừng.

Một cây cầu chỉ có thể được xây dựng giữa hai hòn đảo nếu chúng liền kề nhau theo chiều dọc hoặc chiều ngang, và một trong hai đảo phải có thể truy cập được từ căn cứ trung tâm thông qua các cây cầu đã được xây dựng trước đó.

Số giờ công cần thiết để xây dựng một cây cầu là số lượng cây cầu mà những người thợ xây phải băng qua để đi từ khu rừng gần nhất đến hòn đảo mà bạn đang xây cầu tới, tính cả cây cầu đang được xây dựng. Những người thợ xây chỉ có thể đi lại giữa hai đảo nếu đã có một cây cầu giữa chúng.

Nhà vua đã đảm bảo rằng luôn có ít nhất một cách để kết nối tất cả các hòn đảo.

Hãy viết một chương trình, cho biết bản đồ các hòn đảo, đầu ra là số giờ công tối thiểu cần thiết để kết nối tất cả các đảo.

Hãy xem xét ví dụ sau. Ô màu xanh lá cây biểu thị rừng, màu xám biểu thị đảo trống, và màu xanh dương biểu thị nước.

Một giải pháp tối ưu bắt đầu bằng việc xây dựng các cây cầu sau từ khu rừng ở căn cứ trung tâm.

Chi phí này là \(1 + 2 + 1 + 2 + 3 + 4 = 13\).

Bây giờ, vì khu rừng ở hàng 3, cột 3 đã được kết nối với căn cứ trung tâm, chúng ta có thể xây dựng các cây cầu từ đó. Một giải pháp tối ưu kết nối phần còn lại của các hòn đảo bằng các cây cầu được xây dựng từ khu rừng này.

Chi phí này là \(2 + 1 + 2 + 1 + 2 + 3 = 11\). Tổng chi phí là \(24\), đây là giải pháp tối ưu.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa một số nguyên \(T\), số lượng bộ thử nghiệm. \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu với \(N\), số hàng, và \(M\), số cột, trên một dòng cách nhau bởi dấu cách. \(N\) hàng tiếp theo chứa chính xác \(M\) ký tự mỗi hàng. Ký tự 'T' biểu thị một hòn đảo có rừng, '#' biểu thị một hòn đảo trống, và '.' biểu thị nước.

Dữ liệu ra

Một dòng duy nhất chứa "Case #X: Y", trong đó \(X\) là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(Y\) là số giờ công tối thiểu cần thiết để kết nối tất cả các đảo.

Ràng buộc

• \(1 \le T \le 50\)
• \(2 \le N \le 30\)
• \(2 \le M \le 30\)
• Ô trên cùng bên trái luôn là 'T'.
• Luôn có thể kết nối tất cả các đảo thông qua các cây cầu.

Phân nhóm

• Small dataset (Test set 1): Sẽ có tối đa 2 khu rừng trong lưới bao gồm cả căn cứ trung tâm.
• Large dataset (Test set 2): Không giới hạn số lượng khu rừng trong lưới.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2
T.
T#
4 4
T##.
##.#
.#T#
####
5 5
T#T.#
..#.#
#.###
###.#
T###T

Case #1: 2
Case #2: 24
Case #3: 49

Nguồn

Google Code Jam 2008, Chung kết thế giới, bài Bridge Builders.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.