这是一道交互题,你只需要实现代码中要求的函数。
你的代码需要引用头文件 robot.h
,不需要实现 main
函数。
本题仅支持 C++ 语言提交。
题目描述
塞格德大学的人工智能研究人员正在举办一场机器人编程竞赛。 你的朋友 Hanga 决定参加比赛。由于著名的匈牙利牧羊犬品种 Puli 非常聪明,所以该比赛的目标定为编程实现顶级的 Pulibot。
Pulibot 将在由
考虑一个单元格
- 单元格
被称为单元格 的西邻; - 单元格
被称为单元格 的南邻; - 单元格
被称为单元格 的东邻; - 单元格
被称为单元格 的北邻。
如果
例如,考虑一个迷宫,
唯一的障碍单元格用
从单元格
注意长度为
在比赛中,研究人员设置了一个迷宫,其中至少有一条从单元格
Hanga 不知道迷宫中哪些单元格是空的,哪些单元格是障碍。
你的任务是帮助 Hanga 对 Pulibot 进行编程,使其能够在研究人员设置的未知迷宫中找到从单元格
注意,在题面的最后一部分描述了一个显示工具,该工具可以用于可视化 Pulibot。
Pulibot 说明
对每个单元格
Pulibot 的程序是按一系列步骤执行的。在每一步中,Pulibot 都会识别附近单元格的状态,然后执行一条指令。它执行的指令由识别的状态决定。以下是更准确的描述。
假设在当前步骤开始时,Pulibot位于单元格
- 首先,Pulibot 识别当前状态数组,即数组
, 它包含单元格 及其所有相邻单元格的状态: 表示单元格 的状态。 表示西邻的状态。 表示南邻的状态。 表示东邻的状态。 表示北邻的状态。
- 然后,Pulibot 确定与所识别的状态数组相对应的指令
。 - 最后,Pulibot 执行这条指令:它将单元格
的颜色设置为 ,然后它执行动作 , 是以下动作之一:- 停留 在单元格
; - 移动 到
个邻居之一; - 终止程序。
- 停留 在单元格
例如,考虑下图左侧显示的场景。Pulibot 当前位于单元格
机器人比赛规则
- 在开始时,Pulibot 被放置在单元格
并开始执行其程序。 - 不允许 Pulibot 移动到非空单元格。
- Pulibot 的程序必须在最多
步后终止。 - 在 Pulibot 的程序终止后,迷宫中的空单元格的着色满足以下要求:
- 存在从
到 的最短路径,路径中包括的每个单元格的颜色为 。 - 所有其他空单元格的颜色为
。
- 存在从
- Pulibot 可以在任何空单元格终止其程序。
例如,下图显示了一个可能的迷宫,其中
实现细节
你要实现以下函数:
void program_pulibot()
- 这个函数应该产生 Pulibot 的程序。对于所有
和 的取值以及满足题目约束条件的任何迷宫,该程序应该都能正确工作。 - 对于每个测试用例,此函数只调用一次。
此函数可以调用以下函数来生成 Pulibot 的程序:
void set_instruction(int[] S, int Z, char A)
: 长度为 的数组,用来描述状态数组 : 表示颜色的非负整数 : 表示 Pulibot 动作的单个字符,具体如下:H
: 停留;W
: 移动到西邻;S
: 移动到南邻;E
: 移动到东邻;N
: 移动到北邻;T
: 终止程序。
- 调用此函数指示 Pulibot 在识别状态数组
时应执行指令 。
用相同的状态数组 Output isn't correct
的判定结果。
不需要对每个可能的状态数组 set_instruction
。 但是,如果 Pulibot 后来识别出未设置指令的状态数组,你将得到 Output isn't correct
的判定结果。
program_pulibot
完成后,评测程序会在一个或多个迷宫上调用 Pulibot 的程序。
这些调用不计入解决方案的时间限制。
评测程序不是自适应的,也就是说,每个测试用例的迷宫集合都是预先确定的。
如果 Pulibot 在终止程序之前违反了任何机器人比赛规则,你将得到 Output isn't correct
的判定结果。
函数 program_pulibot
可以调用 set_instruction
如下:
调用 | 对应状态数组 |
---|---|
set_instruction([0, -2, -1, 0, -2], 1, E) |
着色 |
set_instruction([0, 1, -1, 0, -2], 1, E) |
着色 |
set_instruction([0, 1, 0, -2, -2], 1, S) |
着色 |
set_instruction([0, -1, -2, -2, 1], 1, T) |
着色 |
考虑一个场景,
对于这个特定的迷宫,Pulibot 的程序分四个步骤运行。 Pulibot 识别的状态数组和它执行的指令正好依次对应上述对“set_instruction”的四次调用。 这些指令的最后一条指令终止程序。
下图展示了四个步骤每一步之前的迷宫以及终止后的最终颜色。
但是,注意这个由 Output isn't correct
的判定结果。
约束条件
对于每个用来测试Pulibot的迷宫:
子任务
- (6 分)迷宫中没有障碍单元格。
- (10 分)
- (18 分)任意两个空单元格之间恰好有一条路径。
- (20 分)从单元格
到 的最短路径的长度为 。 - (46 分)无额外约束条件。
如果在任何测试用例中,对函数 set_instruction
的调用或 Pulibot 程序的执行不符合“实现细节”中所描述的限制条件,则该子任务的解决方案得分将为
在每个子任务中,你可以通过生成几乎正确的着色来获得部分分数。
形式化地说:
- 如果空单元格的最终颜色满足机器人竞赛规则,则测试用例的解决方案是完整的。
- 如果最终着色如下所示,则测试用例的解决方案是部分的:
- 存在一条从
到 的最短路径,路径中包含的每个单元格的颜色为 。 - 网格中没有其他颜色为
的空单元格。 - 网格中的某些空单元格的颜色既不是
也不是 。
- 存在一条从
如果你对某个测试用例的解决方案既不完整也不部分,则该测试用例的得分将为
在子任务 1-4 中,对每个测试用例来说,完整解决方案的计分为该子任务分数的 100%,部分解决方案的计分为该子任务分数的 50%。
在子任务 5 中,你的分数取决于 Pulibot 程序中所使用颜色的数量。
更准确地说,用 set_instruction
进行的所有调用中
条件 | 分数 (完整) | 分数 (部分) |
---|---|---|
每个子任务的得分是该子任务中所有测试用例上计分的最小值。
评测程序示例
评测程序示例按照以下格式读取输入:
第
其中,
评测程序示例首先调用 program_pulibot()
。如果评测程序示例检测到违反规则的行为,则会打印 Protocol Violation: <MSG>
并终止,其中 <MSG>
是以下错误消息之一:
Invalid array
: 对某些 不成立或者 的长度不是 。Invalid color
: 不成立。Invalid action
:字符 不是H
,W
,S
,E
,N
或T
。Same state array
:用相同的 调用set_instruction
两次或以上。
否则,当 program_pulibot
完成时,评测程序示例将在输入所描述的迷宫中执行 Pulibot 的程序。
评测程序示例产生两个输出。首先,评测程序示例将 Pulibot 动作记录写入工作目录中的文件 robot.bin
。
该文件用作下一节中描述的可视化工具的输入。
其次,如果 Pulibot 的程序未成功终止,评测程序示例将打印以下错误消息之一:
Unexpected state
:Pulibot 识别出一个无法调用“set_instruction”的状态数组。Invalid move
:执行一个动作,导致 Pulibot 移动到一个非空单元格。Too many steps
:Pulibot 执行了 步没有终止程序。
否则,令
显示工具
此任务的附件包含有一个名为 display.py
的文件。
调用时,此 Python 脚本会显示 Pulibot 在由评测程序示例的输入所描述的迷宫中的操作。
为此,工作目录中要有二进制文件 robot.bin
。
要调用该脚本,请执行以下命令。
python3 display.py
一个简单的图形界面将会出现,主要特性如下:
- 你可以观察整个迷宫的状态。 Pulibot 的当前位置以矩形突出显示。
- 你可以通过单击箭头按钮或按热键来浏览 Pulibot 的步骤。 你还可以跳转到特定步骤。
- Pulibot 程序中即将进行的步骤显示在底部。
它显示当前状态数组及将要执行的指令。
在最后一步之后,它或者会显示评测程序的错误消息之一,或者在程序成功终止时显示
Terminated
。 - 对于代表颜色的每个数字,你可以指定视觉背景颜色以及显示的文本。 显示的文本是一个短字符串,应出现在每个具有那个颜色的单元格。你可以通过以下任一方式指定背景颜色和显示的文本:
- 单击
Colors
按钮后在对话框窗口中设置它们。 - 编辑
colors.txt
文件的内容。
- 单击
- 要重新加载
robot.bin
,请使用Reload
按钮。 这可以用来处理robot.bin
的内容发生更改的情况。
关于 Hack 格式
请在数据最后一行后加上数据类型 t/tp
,对应前四个子任务或第五个子任务。
时间限制:
空间限制: