Bridge Builders (Large)

The king wants bridges, and he wants them fast. He owns an $N$ by $M$ grid of land. A river runs between every pair of adjacent cells, so each cell is cut off from its neighbors. Every cell is either an island or a lake, and a lake needs no bridge.

Some of the islands are forests, where trees are plentiful. The top left cell is the base camp, and it is always a forest.

A bridge can be built only between two islands that are vertically or horizontally adjacent. One of those two islands must already be reachable from the base camp over the bridges that are built.

The number of man-hours one bridge costs is the number of bridges the builders cross to get from the nearest forest to the island they are building to, counting the bridge under construction. The builders walk between two islands only when a bridge between them is already built.

The king has made sure that at least one way to connect all the islands exists. Given the map, find the minimum number of man-hours needed to connect every island.

Consider this map. A green tile is a forest, a gray tile is an island without trees, and a blue tile is water.

One optimal plan starts by building these bridges from the forest at the base camp.

They cost $1 + 2 + 1 + 2 + 3 + 4 = 13$ man-hours.

The forest in row 3, column 3 is now connected to the base camp, so bridges can be built from there too. One optimal plan connects the remaining islands with bridges built from that forest.

They cost $2 + 1 + 2 + 1 + 2 + 3 = 11$ man-hours. The whole plan costs 24 man-hours, which is the minimum.

The first line contains an integer $T$, the number of test cases. The first line of each test case contains $N$, the number of rows, and $M$, the number of columns, separated by a space. The next $N$ lines contain exactly $M$ characters each. A T is an island with a forest, a # is an island without trees, and a . is water.

Limits

• $1 \le T \le 50$
• $2 \le N \le 30$
• $2 \le M \le 30$
• The top left cell is always a T.
• Connecting all the islands with bridges is always possible.
• The number of forests in the grid is not limited.

For each test case, print one line in the form Case #X: Y, where $X$ is the 1-based test case number and $Y$ is the minimum number of man-hours needed to connect all the islands.