← 返回题目列表

Codeforces · 921/01

01. 迷宫-1

中文机器翻译题面 查看原题

你有一个机器人,位于一个由 N × M 个单元组成的二维迷宫中。一些相邻的牢房对由墙或门隔开。迷宫本身与外界隔离,周围有墙壁。一些迷宫单元是出口。为了离开迷宫,机器人应该到达任何出口。有些单元格中有钥匙。任何钥匙都可以打开任何门,但门打开后,钥匙仍留在锁中。因此每个密钥只能使用一次。不存在既包含钥匙又包含出口的迷宫单元。此外,在一对相邻的牢房之间不能同时有墙和门。

您需要用 abc 语言编写一个程序(请参阅下面的语言描述),该程序将引导机器人到达其中一个出口。让我们从上到下编号从 0 到 N - 1 的迷宫行,从左到右编号从 0 到 M - 1 的迷宫列。

在 abc 语言中,可以使用以下主要命令:

- move-DIR – 移动到 $$DIR \{up, down, left, right\}$$ 方向上的相邻单元格。向下将行数增加 1,向右将列数增加 1。如果这个方向有墙或关闭的门,则不会发生任何情况。
- open-DIR – 打开当前单元和 DIR 方向相邻单元之间的门。如果这个方向没有门或者门已经打开或者机器人没有钥匙,则什么也不会发生。
- take – 获取当前单元格中的密钥。如果没有钥匙或者机器人已经拿起了钥匙,则什么也不会发生。机器人能够携带任意数量的钥匙。
- 终止 – 终止程序。该命令不是必须使用的。如果不存在,该命令会自动添加到程序末尾。

另外,abc语言还有以下控制命令:

- for-N OPS end – 重复 OPS 命令序列 N 次,0 < N ≤ 100000。每个循环计数器检查都算作机器人执行的命令。
- if-ok OPS1 else OPS2 endif – 如果之前的移动、拿钥匙或开门命令成功,则执行 OPS1 命令序列,否则正在执行 OPS2 命令序列。如果没有先前的命令运行,则将执行序列 OPS1。 If-ok 检查算作机器人执行的命令。
- break – 停止当前的 for 循环。
- continue – 完成当前的 for 循环迭代。

请注意,控制命令和主命令可以任意相互配合。

机器人会依次执行你的命令,直到退出迷宫,或者命令用完,或者执行终止命令,或者执行的命令数量超过限制数量5·106。

在 abc 语言中,每个命令都是一个单独的单词,并且应使用至少一个空格符号与其他命令分隔开。

您应该编写一个程序来打印引导机器人走出迷宫的命令序列。当然,作为一个优秀的程序员,你应该优化这些顺序。

序列中非空格符号的数量不应超过 107。如果您成功找到走出迷宫 i 的出路,您将获得的点数等于:

$${ S _ { i } = \operatorname* { m i n } ( 3 0 0, \operatorname* { m a x } ( 1 0, W _ { i } ( \log _ { 2 } { \frac { Q } { 2 \cdot G _ { i } + O _ { i } } } + \log _ { 2 } { \frac { Q } { L _ { i } } } ) ) ), }$$

- Wi - 迷宫的重量,一些固定常数。
- Gi – 机器人移动次数。
- Oi – 已完成命令的数量。请注意,此数字包括在没有钥匙的牢房中执行的命令,以及应用于已打开的门的打开命令。
- Li – 符号中的序列长度,不包括空格符号和换行符。
- Q = 10·N·M。

如果你的序列没有引导机器人到达出口,你将获得 0 分。你的程序结果将是所有 Si 的总和。您应该最大化这个总和。

所有迷宫都将为您所知并可用。您可以通过任何给定的链接下载带有迷宫的存档,解压文件的密码是aimtechiscool:

1. https://drive.google.com/file/d/1dkIBfW_Gy6c3FJtXjMXZPMsGKRyn3pzp
2. https://www.dropbox.com/s/77jrplnjgmviiwt/aimmaze.zip?dl=0
3.https://yadi.sk/d/JNXDLeH63RzaCi

为了使程序的本地测试更加方便,将提供计算结果的程序(检查器)和迷宫可视化器。该程序是用 python3 编程语言编写的,这就是为什么您需要 python3 解释器以及pillow 库,您可以使用以下命令 pip3 installpillow 来安装它。 pip3 是一个用于 python3 包(库)安装的实用程序。它将随 python3 解释器自动安装。

运行检查器和可视化工具的示例命令:python3immaze.py maze.inrobot.abc --image maze.png。检查器可以与可视化分开运行:python3immaze.pymaze.inrobot.abc。标志--output-log会让你看到机器人每一步的信息:python3immaze.pymaze.inrobot.abc--output-log。注意 python3 可以作为 python 安装在您的计算机上。

要调整图像设置,您可以在程序aimmaze.py的开头编辑常量。

输入

第一行包含整数 i、W、N、M、x0、y0、C、D、K、E。

- 1 ≤ i ≤ 14 – 迷宫编号,检查程序所需。
- 1 ≤ W ≤ 1018 – 迷宫的重量,这是检查程序所需的。
- 2 ≤ N, M ≤ 1000 – 迷宫的高度和宽度。
- 0 ≤ x0 ≤ N - 1,  0 ≤ y0 ≤ M - 1 – 机器人的起始位置 (x0, y0)。
- 0 ≤ C ≤ 2·NM – 墙数。
- 0 ≤ D ≤ 105 – 门数。
- 0 ≤ K ≤ 105 – 键数。
- 1 ≤ E ≤ 1000 – 出口数量。

x 坐标对应于行号,y 坐标对应于列号。 (0, 0) 单元格位于左上角,因此向下方向增加 x 坐标,而向右方向增加 y 坐标。

接下来的 C 行中的每一行都包含 4 个整数,每个整数 x1、y1、x2、y2——基于零的索引中其间有墙的单元格的坐标。保证 |x1 - x2| + |y1 - y2| = 1, 0 ≤ x1, x2 ≤ N - 1, 0 ≤ y1, y2 ≤ M - 1。此外,迷宫的边界周围总是有墙,这在迷宫描述中没有给出。

接下来的每行 D 行都包含与墙壁描述格式相同的门描述。确保门和墙不重叠。

接下来的 K 行中的每一行都包含一对整数,它们是基于零的索引中的关键坐标。

接下来的 E 行中的每一行都包含一对整数,它们是基于零的索引中的退出坐标。

保证机器人的起始位置以及钥匙和出口位于成对的不同单元中。

输出

用 abc 语言打印一个通过给定迷宫的程序。命令必须用至少一个空格符号分隔。您可以对程序使用任意格式。

示例

输入 #1

1 1 30 30 1 1 1 1 1 1
1 1 1 2
2 2 2 3
1 4
9 0

输出 #1

for-1111
take
open-up
open-left
open-right
open-down
move-left
if-ok
for-11
move-left
take
open-up
open-left
open-right
open-down
end
else
move-right
if-ok
for-11
move-right
take
open-up
open-left
open-right
open-down
end
else endif
endif
move-up
if-ok
for-11
move-up
take
open-up
open-left
open-right
open-down
end
else
move-down
if-ok
for-11
move-down
take
open-up
open-left
open-right
open-down
end
else endif
endif
end