题目描述

Edison 是一个机器人，它没有右手和眼睛。作为一个勇敢的机器人，无论是走路还是转弯，它总把左手扶在墙上。因为觉得倒退太危险，Edison 从不向后走。

假设 Edison 发现自己身处一个 $N \times N$ 的正方形迷宫，迷宫由方格外围的墙壁包围。迷宫中，某些格子也是墙壁。Edison 只能沿着东、南、西、北四个方向在两个空格之间移动。为了逃出迷宫，它制定了一个计划：它用左手扶住墙壁，并沿着墙壁行走。

问题是，Edison 能否在至多 $10\,000$ 步内逃出迷宫？如果可行，请输出路径。所谓逃出迷宫，只需最终到达出口格子即可。如果起始格子就是出口，Edison 无需移动便可直接逃出迷宫。

输入格式

输入的第一行给出测试用例的数量 $T$。随后是 $T$ 个测试用例。每个测试用例以一个整数 $N$ 开始，$N$ 是迷宫的大小。接下来的 $N$ 行，每行包含 $N$ 个字符，这些字符可能是 . 或 #。. 代表空格，# 代表墙壁。再接下来一行包含四个整数：$sx, sy, ex, ey$。$(sx, sy)$ 表示 Edison 的起始格子在第 $sx$ 行第 $sy$ 列，$(ex, ey)$ 是迷宫的出口。$(sx, sy)$ 保证位于迷宫的四个角落之一，且初始时 Edison 只能接触到 $4$ 个相邻格子的墙壁（而非 $8$ 个）。$(ex, ey)$ 可以在迷宫中的任何位置。注意左上角为 $(1, 1)$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是：如果 Edison 不能在至多 $10\,000$ 步内到达迷宫出口，则为 "Edison ran out of energy."（不含引号）；否则 $y$ 应为步数，然后紧接着下一行输出包含 $y$ 个字符的路径描述（E 代表东，S 代表南，W 代表西，N 代表北）。无需包含代表转向的字符。我们不关心转向步骤，只需输出 Edison 穿过迷宫的具体移动路径。

3
2
.#
#.
1 1 2 2
5
.##.#
.....
...#.
.###.
...#.
1 1 5 3
3
...
.#.
...
1 1 3 3

Case #1: Edison ran out of energy.
Case #2: 22
SEEENSESSSNNNWWSWWSSEE
Case #3: 4
EESS

提示

注意：

在第二个测试用例中，从起始格子向下移动 $1$ 格后，Edison 仍能在格子 $(1, 2)$ 处用左手扶墙。

在第三个测试用例中，由于初始时 Edison 无法在格子 $(2, 2)$ 处触摸到墙壁，所以它第一步必须向东走。

限制

$1 \le T \le 30$。

$1 \le sx, sy, ex, ey \le N$。

起始格子和迷宫出口永远是空格子。并且起始格子与出口不会是同一个格子。

测试集 1 - 可见

$2 \le N \le 10$。

测试集 2 - 隐藏

$2 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成