0 人解决，0 人已尝试。
0 份提交通过，共有 0 份提交。
9.9 EMB 奖励。
2498. Bridge Builders
单点时限: 2.0 sec
内存限制: 256 MB
The king wants bridges built and he wants them built as quickly as possible. The king owns an N by M grid of land with each cell separated from its adjacent cells by a river running between them and he wants you to figure out how many man-hours of work it will take to build enough bridges to connect every island. Some cells are actually lakes and need not have a bridge built to them.
Some of the islands are forests where trees are abundant. Located in the top left corner is the base camp, which is always a forest.
A bridge can only be built between two islands if they are vertically or horizontally adjacent, and one of the islands is accessible from the base camp through the bridges that are already built.
The number of man-hours it takes to build a bridge is the number of bridges the builders have to cross to get from the nearest forest to the island you’re building to, including the bridge being built. Builders can only walk between two islands if there is already a bridge between them.
The king has already ensured that there is at least one way to connect all the islands.
Write a program that, given a map of the islands, will output the minimum number of man-hours required to connect all islands.
Consider this example.
输入格式
The first line of the input contains an integer T(1 ≤ T ≤ 50), the number of test cases. T test cases follow. Each test case will begin with N(2 ≤ N ≤ 30), the number of rows, and M(2 ≤ M ≤ 30), the number of columns, on one line separated by a space. N rows follow that contain exactly M characters each. A ‘T’ indicates an island with a forest, a ‘#’ indicates an island, and a ‘.’ indicates water.
The top left cell will always be a ‘T’
It will be possible to connect all islands through bridges
There will be no limit on the number of forests in the grid.
输出格式
A single line containing “Case #X: Y”, where X is the 1-based case number, and Y is the minimum number of man-hours needed to connect all islands.
样例
Input
2 4 4 T##. ##.# .#T# T### 5 5 T#T.# ..#.# #.### ###.# T###T
Output
Case #1: 24 Case #2: 49
题目标签