题目描述

糟糕！邪恶巫师 Nocoproco 把你关进了一座无法逃离的地下城。既然短时间内也出不去，不如把地下城探索清楚，画出完整地图。

地下城中没有怪物，探索总体比较安全，但有一些麻烦：地下城中最多有两个隐藏的活板门。走到活板门所在格子时，你会立刻掉下去，并出现在地下城的另一个位置。

地下城是一个矩形网格，每个格子可能是：

• 墙；
• 普通空地；
• 活板门。

你无法直接识别自己是否到过某个位置，也很容易迷失方向；不过你始终能辨认东西南北。

当你位于一个普通空地时，你只能看出上下左右四个相邻格子中哪些是墙，哪些可以走。你可以走向任意一个不是墙的相邻格子。

当你走入一个活板门时，在掉落前，你仍然来得及观察活板门四周四个格子的情况；随后你会被传送到这个活板门对应的终点。活板门的终点一定是普通空地，不会是另一个活板门。两个活板门的终点位置互不相同。起始位置既不是活板门，也不是任何活板门的终点。

保证从地下城中的任意可达位置都可以到达任意其他可达位置；这个过程可能需要经过活板门。同时，若把活板门都看成普通空地，地下城仍然是一个连通区域。

你的任务是编写程序探索地下城，并输出完整地图。

交互格式

本题为交互题，交互按轮进行。每一轮中，评测器先向你的程序输出当前位置附近的信息，然后你的程序输出一个操作。

评测器输入给程序的信息

每轮开始时，评测器输出一行。

这一行首先包含 4 个字符 c_N c_E c_S c_W，依次表示当前位置的北、东、南、西四个相邻格子的情况：

• # 表示该方向是墙；
• . 表示该方向可以走。

随后同一行会包含一个字符串：

• ok：当前位置不是活板门；
• trap：当前位置是活板门。

如果当前位置是活板门，则这一行还会包含第三个字符串，表示活板门终点位置四周的情况，格式同样是北、东、南、西四个字符。

也就是说，交互器给出的信息有两种形式：

NESW ok
NESW trap NESW

其中 NESW 是长度为 4 的字符串，由 # 和 . 组成。

程序输出的操作

你的程序可以输出两类操作。

第一类是移动到相邻格子，输出单独一行：

N

或

E

或

S

或

W

分别表示向北、东、南、西移动一步。你不能尝试走进墙，否则会被判为 Wrong Answer。

第二类是结束探索并报告完整地图。此时先输出一行：

done

然后输出完整地图。地图必须是包含所有可见墙格的最小矩形。先输出一行两个整数：

h w

表示地图高度和宽度。接下来输出 h 行，每行恰好 w 个字符，从北到南、从西到东表示地图。

地图中字符含义如下：

• #：墙，或地下城外不可达的格子；
• S：起始位置；
• A、B：两个活板门的位置；
• a、b：对应活板门的终点位置；
• .：其他可走格子。

A 与 B 的命名可以互换，但 a 必须是 A 的终点，b 必须是 B 的终点。如果只有一个活板门，你可以把它标成 A 或 B。

输出完整地图后，交互结束，程序应立即退出。

约束条件

• 地下城中最多有 500 个可达位置。
• 你的程序最多可以移动 $10^5$ 步。
• 地下城中最多有 2 个活板门。
• 每次输出操作后请刷新标准输出缓冲区。

在 C++ 中，可以使用：

cout << endl;

或显式调用：

cout.flush();

样例交互 1

其中 < 开头的行表示评测器输出给程序的信息，> 开头的行表示程序输出。

<#.#. ok
>E
<#.#. trap .###
>N
<##.. trap #.##
>E
<#.#. ok
>E
<#.#. ok
>E
<#.#. trap .###
>done
>4 7
>#######
>#b.SAB#
>#####a#
>#######

对应地图为：

4 7
#######
#b.SAB#
#####a#
#######

样例交互 2

<.##. ok
>W
<..## ok
>N
<#..# ok
>E
<##.. ok
>done
>4 4
>####
>#..#
>#.S#
>####

对应地图为：

4 4
####
#..#
#.S#
####

本地测试工具说明

本题提供本地交互测试工具 testing_tool.py，用于帮助选手在本地调试交互程序。该工具只是本地调试辅助文件，不是正式评测器。正式评测时，选手程序会与 Hydro OJ 的交互器通信。

使用方法

先编译你的程序。例如 C++ 程序可以使用：

g++ -std=c++17 -O2 -pipe -o main main.cpp

然后运行：

python3 testing_tool.py ./main

如果没有指定地图文件，测试工具会使用样例交互 1 中的默认地图。

也可以使用自定义地图：

python3 testing_tool.py -f mymap.txt ./main

其中 mymap.txt 的格式应与本题最终输出地图的格式一致。例如：

4 7
#######
#b.SAB#
#####a#
#######

其他语言示例

Java：

javac Main.java
python3 testing_tool.py java Main

Python：

python3 testing_tool.py python3 main.py

Windows 下也可以类似运行：

python testing_tool.py main.exe

注意事项

1. 你的程序每次输出移动方向或 done 后，必须及时刷新输出缓冲区。

   • C++ 可使用 endl 或 cout.flush()；
   • C 可使用 fflush(stdout)；
   • Python 可使用 print(..., flush=True)。

2. testing_tool.py 只会模拟交互过程并检查最终地图是否正确，不保证完全覆盖正式评测中的所有情况。

3. 自定义地图需要满足题目要求。测试工具只会做部分合法性检查，例如：

   • 恰好有一个 S；
   • A 和 a 数量匹配；
   • B 和 b 数量匹配；
   • 地图字符合法。

   它不会完整检查地图是否连通、是否没有死胡同、边界是否全为墙等条件。

4. 如果程序走进墙、输出非法方向、步数超过限制，测试工具会报错并终止。

5. 当测试工具输出：

[*] OK, solution correct!

表示你的程序在当前地图上通过了本地测试。

Hydro OJ 说明

本题应按交互题配置。测试数据文件中的内容是完整地图，仅供交互器读取，选手程序不会直接读到完整地图。交互器会根据选手的移动逐步返回四周信息，并在选手输出 done 后检查最终地图是否正确。

@下发文件