SP20041 HIPPO - Hippo and Bloody Jungle

河马和他的两个朋友在丛林中迷失了方向。现在的丛林十分危险，里面不仅有许多隧道，还潜伏着一些凶猛的动物，这些动物一般出现在标记为 'D' 的危险区域。河马和他的朋友们希望能够以最快的速度，即用最少的时间，抵达安全地点（标记为 '#' 的地方）。 ### 问题描述 在这道题中，你会得到一个用网格表示的丛林地图。在地图上，‘A’, ‘B’, ‘C’ 分别代表河马和他的两位朋友的位置。‘D’ 表示危险区域，此处禁止任何人停留。‘#’ 代表安全区域。此外，网格中还会有一些字母（E-Z）标识的隧道，这些字符可能出现多次。如果有人到达某个隧道，他可以传送到其他任何相同字母标识的隧道，也可以移动到相邻的格子（八个方向都有可能）。他们从普通地点移动到相邻格子需要花费 1 单位时间。问题是，他们能否全部到达安全区域？如果能，所需的最短时间是多少？ ### 输入格式 输入的第一行为一个整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个正整数 $H$ 和 $W$，分别表示网格在 $y$ 和 $x$ 方向上的格数。$W$ 和 $H$ 均不超过 20。接下来有 $H$ 行数据，每行包含 $W$ 个字符，每个字符表示一个格子的状态，具体如下： 1. **'.'** – 普通地点。 2. **'#'** – 安全地点。 3. **'A', 'B', 'C'** – 河马和朋友们的初始位置。 4. **'D'** – 危险地点。 5. **'E-Z'** – 表示隧道。 ### 输出格式 对于每个测试用例，输出一个结果：先输出案例编号，然后输出到达所有安全地点所需的最短时间。如果无法使所有人安全到达，请输出 `impossible`。 ### 数据范围与提示 - $1 \le T \le 100$ - $1 \le H, W \le 20$ ### 样例输入 ``` 2 5 6 C..E#. .D.... F..E.. .D..A. .B.D.F 4 4 C.D# .FDD A..E .B.F ``` ### 样例输出 ``` Case 1: 4 Case 2: impossible ``` **本翻译由 AI 自动生成**

无

无