AT_kupc2019_i.encode/decode 2019

注意：这是一道包含交互元素的题目。

您将获得一个在 $0$ 到 $10^{18}$ 之间的整数 $X$。

请仔细阅读下列说明，并编写两个程序：一个用于编码整数 $X$ 的 encode 程序，另一个用于解码以找回 $X$ 的 decode 程序。

如果 decode 程序能仅通过 encode 程序编码后的信息准确恢复 $X$，则结果视为正确。

encode 程序

在 encode 程序中，您需要将输入的整数 $X$ 编码为一个 $150 \times 150$ 的网格 $H$。

首先，您会得到一个整数 $X$ 和一个 $150 \times 150$ 的初始网格 $G$。网格 $G$ 中的元素可能是空格 . 或墙壁 #，这些墙壁是根据特定规则生成的。

您需要通过以下三种操作之一对网格 $G$ 中的每一个空格 . 进行处理，进而生成并输出网格 $H$：

• 将其替换为墙壁 #；
• 将其替换为 S 格 S；
• 保持为空格 .。

重要的是，在网格 $H$ 中，S 格必须且只能有一个。

decode 程序

在 decode 程序中，您的任务是从网格 $H$ 的信息中解码出整数 $X$。

网格 $H$ 的信息并不会直接提供给您，而是让您控制一个在网格 $H$ 上的机器人进行一系列操作。

我们将网格中的第 $i$ 行第 $j$ 列的格子称为格子 $(i, j)$。初始时，机器人位于S格。通过多次以下的**“操作”**，您可以解码出整数：

• 指示机器人向上下左右四个方向中的一个移动。
• 机器人会尝试从当前位置向指定方向的相邻格子移动。
  • 如果机器人当前在格子 $(i, j)$，那么：
    • 上：移动至 $(i-1, j)$；
    • 下：移动至 $(i+1, j)$；
    • 左：移动至 $(i, j-1)$；
    • 右：移动至 $(i, j+1)$。
• 机器人移动的条件是目的地格子不是墙壁 #，且该目的地不在网格之外。否则，它会停留在原地。
• 随后，您会收到关于机器人是否在 S 格上的反馈。
• 您并不知道机器人是否成功移动。

在进行一系列**“操作”**后，您需要输出您解码出的整数 $X$。

初始网格生成

初始网格 $G$ 共包括 $3800$ 个随机分布的墙壁 #。

保证每一堵墙周围8个格子中都不会有其他的墙。

具体生成步骤如下：

• 最初整个网格均为空格 .。
• 不断随机选择周围格子均为.的空格，替换为墙壁 #，直到放置了 $3800$ 个墙壁。
• 这一过程中如果无法再放置墙壁，则放弃该网格，重新生成整个网格。
• 重复这一过程，直到成功放置 $3800$ 个墙壁。

这种方法生成的初始网格样本，我们提供了 50个样本。

注意：提供的样本并不一定用于实际测试。

约束

• $0 \leq X \leq 10^{18}$，$X$ 为随机选择。
• 网格尺寸为 $150 \times 150$。
• 初始网格 $G$ 包含 $3800$ 墙壁 #。
• 墙壁周围的 8 个格子中没有其他墙。
• 每次提交都会生成新的整数 $X$ 和初始网格 $G$。

部分得分

本题设置了部分分数。

对于每次提交所生成的 $25$ 个测试用例中任何一例：

• 若在 $65000$ 次或更少的**“操作”**内正确解码，您将得到 $10$ 分；同时
• 若在 $6500$ 次或更少的**“操作”**内正确解码，您将额外得到 $390$ 分。

提交

将 encode 程序和 decode 程序组合为一个文件进行提交。

根据下面的“评测说明”，提交的程序会分别以编码和解码模式被调用各一次。

程序启动时会输入一个字符串以指示当前是编码还是解码。

输入（encode 程序）

输入是通过标准输入以以下形式给出的。

第一行为字符串 encode。

第二行为整数 $X$，第三行及以后各行为初始网格 $G$。

$G$ 中的格子 $(i, j)$ 由字符 $G_{i,j}$ 表示。

• 若格子 $(i, j)$ 为空格，则 $G_{i,j}$ 是 .；
• 若格子 $(i, j)$ 为墙壁，则 $G_{i,j}$ 是 #。

无字符间空格：

encode
X
G_{1,1}G_{1,2}...G_{1,150}
:
G_{150,1}G_{150,2}...G_{150,150}

输出（encode 程序）

请按照以下格式将网格 $H$ 输出到标准输出。

网格 $H$ 中的格子 $(i, j)$ 用字符 $H_{i,j}$ 表示。

• 若格子 $(i, j)$ 为空格，则 $H_{i,j}$ 是 .；
• 若格子 $(i, j)$ 为墙壁，则 $H_{i,j}$ 是 #；
• 若格子 $(i, j)$ 为 S 格，则 $H_{i,j}$ 是 S。

无字符间空格：

H_{1,1}H_{1,2}...H_{1,150}
:
H_{150,1}H_{150,2}...H_{150,150}

输入输出（decode 程序）

程序将以以下形式从标准输入接收字符串 decode：

decode

随后进行一系列**“操作”。在每次“操作”**中，请按照以下格式输出您希望机器人的移动方向：

方向用 $C$ 表示，可能取 U, D, L, R 中的一个，分别表示上下左右四个方向。

? C

对该**“操作”**的响应将按照以下格式从标准输入给出。

反馈中用 $J$ 表示机器人是否在S 格上：

• 如果在，则 $J$ 为 S；
• 如果不在，则 $J$ 为 .。

J

最后，请按照以下格式输出您解码出的整数 $X$：

! X

评测说明

评测将按照下面的步骤进行：

• 生成随机整数 $X$ 和初始网格 $G$。
• 编码环境中启动提交的程序。
• 将输入传给编码环境的程序，不发送EOF。
• 程序输出正确的编码后，可正常终止程序。
• 输入无效网格将被判为错误。
• 解码环境中启动提交的程序。
• 与解码程序交互，直至其结束。
• 如果在时间限制内获得正确输出，则判定为正确，否则判定错误。

注意事项

• 每次输出后请刷新标准输出，否则可能会导致超时。
• 输出网格 $H$ 和整数 $X$ 后，请立即终止程序，否则行为未定义。
• 输出格式不符合要求时，评测结果未定义。
• 程序不得执行任何未明示批准的通信操作。

输入样例（encode 程序）

此例中，网格 $G$ 为 $20 \times 20$，实际为 $150 \times 150$。

墙壁数量为 $70$，实际应为 $3800$。

encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..

输出样例（encode 程序）

此例中，网格 $H$ 为 $20 \times 20$，实际为 $150 \times 150$。

####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################

输入输出样例（decode 程序）

这是在上面的编码示例后的解码过程的示例。

输入 输出 备注

decode

解码开始。机器人在 S 格坐标 $(2, 2)$。

? R

机器人向右移动到空格 $(2, 3)$。

.

机器人位于空格中。

? U

机器人尝试往上到墙 $(1, 3)$，但失败，仍在 $(2, 3)$。

.

机器人仍然在空格中。

? L

机器人移动回 S 格 $(2, 2)$。

S

机器人此时在 S 格。

! 239

输出 $X$，过程结束. **“操作”**次数为 $3$ 次。

本翻译由 AI 自动生成