Description

国王希望尽快建造桥梁。他拥有一块 $N$ 行 $M$ 列的土地，每个格子之间由河流隔开，他希望你计算出连接所有岛屿所需的最少人工时数。有些格子实际上是湖泊，不需要建桥。

部分岛屿上是森林，树木丰富。左上角的格子是大本营，且总是森林。

桥梁只能建在两个垂直或水平相邻的岛屿之间，并且其中一个岛屿必须能够通过已建好的桥梁从大本营到达。

建造一座桥所需的人工时数等于从最近的森林到你要建桥的岛屿所需经过的桥数（包括正在建造的这座桥）。工人只能在已有桥梁连接的岛屿之间行走。

国王已经确保所有岛屿之间至少有一条可连接的路径。

请编写程序，给定岛屿地图，输出连接所有岛屿所需的最少人工时数。

例如，绿色格子表示森林，灰色表示普通岛屿，蓝色表示水域。

一种最优解是首先从大本营森林建造如下桥梁：

其代价为 $1 + 2 + 1 + 2 + 3 + 4 = 13$。

现在，由于第 $3$ 行第 $3$ 列的森林已与大本营相连，我们可以从那里继续建桥。一种最优解是从该森林连接剩余的岛屿：

其代价为 $2 + 1 + 2 + 1 + 2 + 3 = 11$。总代价为 $24$，这是最优解。

Input Format

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

Output Format

输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 为测试用例编号（从 $1$ 开始），$Y$ 为连接所有岛屿所需的最少人工时数。

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

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

Hint

数据范围

• $1 \leq T \leq 50$
• $2 \leq N \leq 30$
• $2 \leq M \leq 30$
• 左上角格子总是 'T'
• 保证所有岛屿都可以通过桥梁连通

小数据（8 分，测试点 1 - 可见）

• 地图中森林数量最多为 $2$（包括大本营）

大数据（17 分，测试点 2 - 隐藏）

• 地图中森林数量不受限制。

由 ChatGPT 4.1 翻译