桥梁建造者 - 题目

国王想要建造桥梁，并且希望建造速度越快越好。国王拥有一块 $N \times M$ 的土地网格，每个单元格与其相邻单元格之间都有河流隔开。他希望你计算出建造足够的桥梁以连接所有岛屿所需的工时。有些单元格实际上是湖泊，不需要为其建造桥梁。

有些岛屿是树木茂密的森林。位于左上角的单元格是大本营，它总是一片森林。

只有当两个岛屿在垂直或水平方向上相邻，且其中一个岛屿可以通过已建成的桥梁从大本营到达时，才能在这两个岛屿之间建造桥梁。

建造一座桥所需的工时等于建筑工从最近的森林到达目标岛屿所需要经过的桥梁数量（包括正在建造的那座桥）。建筑工只能在已有桥梁连接的两个岛屿之间行走。

国王已经确保至少有一种方法可以连接所有岛屿。

编写一个程序，给定岛屿地图，输出连接所有岛屿所需的最小工时。

考虑这个例子。绿色方块表示森林，灰色表示普通岛屿，蓝色表示水域。

一种最优解是从大本营森林开始建造以下桥梁。

其成本为 $1 + 2 + 1 + 2 + 3 + 4 = 13$。

现在，由于第 3 行第 3 列的森林已连接到大本营，我们可以从那里开始建造桥梁。一种最优解是从这片森林出发连接其余岛屿。

其成本为 $2 + 1 + 2 + 1 + 2 + 3 = 11$。这使得总成本为 $24$，即为最优解。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个由空格分隔的整数 $N$（行数）和 $M$（列数）。接下来的 $N$ 行，每行包含恰好 $M$ 个字符。'T' 表示森林岛屿，'#' 表示普通岛屿，'.' 表示水域。

输出一行 "Case #X: Y"，其中 $X$ 是从 1 开始的用例编号，$Y$ 是连接所有岛屿所需的最小工时。

$1 \le T \le 50$

$2 \le N \le 30$

$2 \le M \le 30$

左上角的单元格始终为 'T'。

保证可以通过桥梁连接所有岛屿。

小型数据集（测试集 1 - 可见；8 分）

网格中最多包含 2 片森林（包括大本营）。

大型数据集（测试集 2 - 隐藏；17 分）

网格中森林的数量没有限制。

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

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

QOJ.ac