P14667 [ICPC 2025 Seoul R] Adventurer Dabi

著名的银河系冒险家 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 相同时的样例交互。

无

无

要刷新输出缓冲区，你需要在写入命令和换行后立即执行以下操作： - 在 C 语言中使用 `fflush(stdout)`； - 在 C++ 中使用 `std::cout