SP9936 CGW - Construct the Great Wall

有一个地图，每个测试用例描述一张地图。地图由若干行和列组成，其中： - `'o'` 表示城市 - `'.'` 表示空地 - `'x'` 表示敌人 你的任务是为地图上的城市构建一座最短的“长城”，将地图上的城市用最少的“墙”连接起来。

第一行包含一个整数 $T$ 表示测试用例的数量（$1 \le T \le 50$）。 每个测试用例开始于一行两个整数 $H$ 和 $W$，表示地图的行数和列数（$1 \le H, W \le 8$）。接下来的 $H$ 行中，每行包含 $W$ 个字符，描述这张地图。 可以保证每张地图上至少有一座城市。

对于每个测试用例，输出一行：`Case #X: Y`。其中，$X$ 代表测试用例的编号（从 1 开始），$Y$ 表示构建该长城的最短长度。如果无法连接所有城市，则输出 -1。 希望以上描述能帮助你理解问题的要求，并指导你如何构建长城。 **本翻译由 AI 自动生成**