SP25789 LASER - Laser Maze

随着年纪的增长，经典迷宫逐渐变得不再神秘。不过，如果加上激光，那就另当别论了。我们的目标是在迷宫中从起点找到通往终点的路径。而在「激光迷宫」中，你还必须避开激光炮台的袭击。 激光炮台是固定不动的柱子，它不仅阻挡你的去路，还会从某一侧发射激光。每当你移动一步（上、下、左、右），迷宫里的每个激光炮台都会顺时针旋转 90 度，然后在其朝向的方向瞬间发射激光。显然，如果你站在这些激光的路径上，你的旅行就会到此为止。相对的，墙壁则只是简单地阻挡你的移动，并不会发射激光。 虽然激光很强大，但无法穿透墙壁或其他激光炮台。同时，由于激光炮台会随你的移动而旋转，你无法通过原地不动来避开攻击。如果你到达终点，然而立刻被激光击中，那么一切努力都会白费，所以确保安全到达终点至关重要。

输入首先给出一个整数 $T$ 表示需要探索的迷宫数目。接下来每个迷宫会给出一行包含两个整数 $M$ 和 $N$，分别表示迷宫的高度和宽度。接下来的 $M$ 行，每行包含 $N$ 个字符，描述迷宫的布局： - . 表示空地 - \# 表示墙壁 - S 表示起始位置 - G 表示终点位置 - < > ^ v 表示激光炮台，分别指初始朝向为左、右、上、下的激光炮台

对于第 $i$ 个迷宫，请输出一行：格式为 "Case #$i$: "，后接不被激光击中的最少步数；如果无法安全到达终点，则输出 "impossible"。 ## 数据范围和提示 - $1 \le T \le 10$ - $1 \le M, N \le 50$ - 每个迷宫中恰好有一个 'S' 和一个 'G'。 **本翻译由 AI 自动生成**