Description

著名的银河系冒险家 Dabi 进入了一座被遗忘已久的地下城市，据说其中隐藏着一件古老的宝藏。在漆黑一片的隧道中，她必须在城市坍塌前找到钥匙并抵达宝藏箱。

整座城市可以表示为一个 $h \times w$ 的网格 ($3 \le h, w \le 16$)。网格中的每个格子属于以下类型之一：

• 空地：可以通行的通道。
• 墙：坚固的方块，无法进入。
• 传送格：古代装置，能够瞬间连接两个遥远的地点。

关于这座地下城市，已知以下事实：

• 网格边界上的每个格子（即最上/最下行，或最左/最右列）都是墙。
• 所有墙格通过上下左右四个方向相连——即它们形成一个单一的 4-方向连通块。
• 所有空单元格相连，形成一个单一的 4-方向连通块，并被墙所包围。
• 对于每个传送格，其所有八个相邻的格子都是空地。
• 每个传送格恰好属于一个传送对。如果 Dabi 从任何方向踏入一个传送格，她会被立即传送到其配对的格子，然后沿着她进入传送格的相同方向再移动一格。此过程不会触发另一次传送。
• 每个传送对都用大写字母 A, B, C, D, E, F 中的一个进行标记。因此，最多总共有 $6 \times 2 = 12$ 个传送格。
• 恰好有一把钥匙和一个宝藏箱，各自放置在不同的空地上，但都不在 Dabi 的起始位置。

:::align{center}

图 1. 地下城市的一个示例配置 ($h = 7; w = 9$)，包含两个传送对 A 和 B。 :::

Dabi 可以执行以下两种操作：

• 移动到四个相邻格子之一，该格子不是墙。传送及随后的额外移动被视为“进入传送格”的一部分，不计为单独的操作。
• 如果她位于放有钥匙的格子上，拾起钥匙。

每次操作前后，Dabi 总是站在一个空地上。

图 1 展示了地下城市的一个示例，其中 $h = 7$, $w = 9$。传送对 A 连接着标记为字母 A 的两个格子，传送对 B 连接着标记为字母 B 的两个格子。请注意，图 1 对应了附件 sample.in 文件中描述的城市。

如图 2 所示，传送过程的工作原理如下。在图 2(a) 中，Dabi 站在传送格 A 东侧的格子上。当地向西移动时，她踏入了标记为 A 的传送格，立即被传送到其配对格子，然后向西额外移动一步，结果如图 2(b) 所示。

:::align{center}

图 2. 传送过程的图示。(a) Dabi 站在传送格 A 正东的格子。(b) 向西移动后，她踏入传送格 A，被传送到其配对格子，然后向西额外移动一步。 :::

当 Dabi 拾起钥匙时，城市开始坍塌。从那一刻起，她必须用尽可能少的操作次数到达宝藏格。任何更长的路线都会导致尝试失败。

Dabi 携带一个可靠的指南针，总是能分辨东西南北。通过触摸周围的墙壁，她能感知到四个方向中每一个方向上的相邻格子是否是墙。然而，她最初并不知道自己的坐标或城市的整体布局。在任何时刻，她也能感知她当前所在的格子是否包含钥匙或宝藏。她可以站在钥匙格上而不立即拾取它。

你的任务是引导 Dabi 穿越城市，获取钥匙，然后抵达宝藏箱，遵守所有移动规则。请编写一个程序，通过一系列命令与交互器进行交互来完成此任务。

交互

这是一个交互式问题。你提交的程序将与评测服务器内的交互器进行交互，交互器会读取你程序的输出并向其写入输入。你的程序必须通过打印命令来控制 Dabi，并读取交互器的回复。在每行输出之后，必须立即刷新输出缓冲区。

初始输入

交互开始时，交互器会提供关于 Dabi 当前格子的信息。该信息以单行形式给出，包含六个无空格的字符：

• 每个字符是 '0' 或 '1'。
• 对于前四个字符，'1' 表示该方向的相邻格子是墙，'0' 表示不是墙。方向的顺序是北、南、东、西。
• 第五个字符是 '1' 表示钥匙位于 Dabi 当前格子且尚未被拾取；否则为 '0'。
• 第六个字符是 '1' 表示宝藏箱位于 Dabi 当前格子；否则为 '0'。
• 由于钥匙和宝藏箱位于不同的格子，第五和第六个字符不会同时为 '1'。

例如，"100010" 表示北边有墙，其他三个方向开放，未拾取的钥匙在当前格子，并且没有宝藏。

命令

你的程序可以重复输出以下命令之一，直到交互器输出 "correct" 或终止交互。

1. "N"、"S"、"E" 或 "W"
   • 向选定的方向移动一步——"N"（北）、"S"（南）、"E"（东）或"W"（西）。目标格子不能是墙。如果目标格子是传送格，Dabi 将根据上述规则被传送。
   • 尝试移动到墙上会导致交互器输出 "wrong"。
2. "K"
   • 拾取当前格子上的钥匙。此操作后，宝藏箱打开，从此刻起 Dabi 必须用尽可能少的操作次数到达宝藏格。
   • 如果当前格子上没有未拾取的钥匙，交互器输出 "wrong"。

每个命令必须独占一行打印并立即刷新。发出的命令总数不得超过 $230,611$。

交互器响应

每次操作后，交互器响应如下：

• 如果 Dabi 已经拾取了钥匙并且刚刚以最少可能操作数到达了宝藏格，交互器输出 "correct"。
• 如果任何规则被违反（例如，命令格式错误、移动无效、尝试拾取不存在或已收集的钥匙、总操作数超过 $230,611$，或在拾取钥匙后未通过最少可能操作数的路线到达宝藏），交互器会立即终止交互。
• 否则，交互器输出一个六字符的字符串，描述 Dabi 新的当前格子，格式与初始输入相同。

收到 "correct" 意味着你的程序已成功完成任务，应正常终止。打印每条命令后请勿忘记刷新输出。

城市布局在整个交互过程中是固定的；交互器不是自适应的。

交互器使用的时间和内存也会计入你程序的执行时间和内存使用。你可以假设交互器最大使用时间为 1 秒，最大内存为 64 MiB。

以下展示了当城市布局和 Dabi 初始位置与图 1 相同时的样例交互。

101000

000000

000000

010000

010110

010100

000000

010100

000100

correct

W

W

S

W

K

N

W

N

E

Hint

要刷新输出缓冲区，你需要在写入命令和换行后立即执行以下操作：

• 在 C 语言中使用 fflush(stdout)；
• 在 C++ 中使用 std::cout << std::flush；
• 在 Java 或 Kotlin 中使用 System.out.flush()；
• 在 Python 中使用 sys.stdout.flush()。

提供了一个测试工具来帮助你开发解决方案，但使用它不是强制性的。如果你希望使用它，可以从 DOMjudge 题库页面下载附件 testing_tool.py。你可以运行该测试工具来查看你的程序针对特定城市布局的交互情况。无论你的程序使用何种语言，都可以按如下方式使用此测试工具。

用法：python3 testing_tool.py -f <输入文件> <程序>

使用 -f 参数指定输入文件，例如 input.in。

输入文件格式：第一行包含两个整数 $h$ 和 $w$。接下来的 $h$ 行每行包含一个长度为 $w$ 的字符串，描述城市地图。每个字符代表一种格子类型，如下所示：

• '#': 墙格。
• '.': 空地。
• 'k': 包含钥匙的空地。
• 't': 包含宝藏箱的空地。
• 'v': Dabi 初始站立的空地。
• 'A', 'B', 'C', 'D', 'E', 'F': 传送格，每个字母代表一个传送对。

示例：图 1 所示城市表示如下：

7 9
#########
###...###
#...A.v##
#.B.....#
#...A.Bt#
##k.....#
#########

该工具按原样提供，你可以随意对其进行任何修改或增强。请注意，不能保证通过测试工具的程序一定会被接受。例如，测试工具不会验证 Dabi 在拾取钥匙后是否以最少可能操作数到达宝藏箱；它只报告进行了多少次操作。

如果你有一个存储在名为 "sol.cpp" 文件中的 C++ 解决方案，你必须先使用 "g++ sol.cpp -o sol" 进行编译，然后通过以下命令调用测试工具：

python3 testing_tool.py -f input.in ./sol

如果你有一个 Python 解决方案，通常使用 "pypy3 solution.py" 运行，你可以通过以下命令调用测试工具：

python3 testing_tool.py -f input.in pypy3 solution.py

如果你有一个 Java 解决方案，通常使用 "java MyClass" 运行，你可以通过以下命令调用测试工具：

python3 testing_tool.py -f input.in java MyClass

如果你有一个 Kotlin 解决方案，通常使用 "kotlin SolutionKt" 运行，你可以通过以下命令调用测试工具：

python3 testing_tool.py -f input.in kotlin SolutionKt

翻译由 DeepSeek V3 完成