{"raw_statement":[{"iden":"background","content":"这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。\n\n本题仅支持 C++ 语言提交。\n\n---\n\n由于某些技术原因，你可能需要在源代码的开头加入以下内容：\n\n```cpp\n#include <vector>\n\nvoid program_pulibot();\nvoid set_instruction(std::vector<int> S, int Z, char A);\n```"},{"iden":"statement","content":"塞格德大学的人工智能研究人员正在举办一场机器人编程竞赛。\n你的朋友 Hanga 决定参加比赛。由于著名的匈牙利牧羊犬品种 Puli 非常聪明，所以该比赛的目标定为编程实现顶级的 Pulibot。\n\nPulibot 将在由 $(H+2) \\times (W+2)$ 网格组成的迷宫中进行测试。\n网格的行从北到南编号为 $-1$ 到 $H$，网格的列从西到东编号为 $-1$ 到 $W$。\n我们将位于网格的第 $r$ 行和第 $c$ 列的单元格（$-1 \\le r \\le H$, $-1 \\le c \\le W$）称为单元格 $(r,c)$。\n\n考虑一个单元格 $(r,c)$ （$0 \\le r \\lt H$，$0 \\le c \\lt W$），和它**相邻**的有 $4$ 个单元格。\n\n* 单元格 $(r,c-1)$ 被称为单元格 $(r,c)$ 的**西邻**；\n* 单元格 $(r+1,c)$ 被称为单元格 $(r,c)$ 的**南邻**；\n* 单元格 $(r,c+1)$ 被称为单元格 $(r,c)$ 的**东邻**；\n* 单元格 $(r-1,c)$ 被称为单元格 $(r,c)$ 的**北邻**。\n\n如果 $r=-1$ 或 $r=H$ 或 $c=-1$ 或 $c=W$ 成立，则单元格 $(r,c)$ 称为迷宫的**边界**。每个不是迷宫边界的单元格要么是**障碍**，要么是**空的**。\n此外，每个空单元格都有一个**颜色**，由 $0$ 和 $Z_{\\text{MAX}}$ 之间的非负整数表示，包括 $0$ 和 $Z_{\\text{MAX}}$。最初，每个空单元格的颜色为 $0$。\n\n例如，考虑一个迷宫，$H=4$， $W=5$， 包含一个障碍单元格 $(1,3)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/h649yqfv.png)\n\n唯一的障碍单元格用 $\\times$ 表示。迷宫的边界单元格被阴影覆盖。\n每个空单元格中的数字表示它的颜色。\n\n从单元格 $(r_0, c_0)$ 到单元格 $(r_\\ell, c_\\ell)$ 的长度为 $\\ell$（$\\ell\\gt 0$）的**路径**\n是一个**空**单元格序列 $(r_0,c_0), (r_1, c_1), \\ldots, (r_\\ell, c_\\ell)$，序列中的空单元格两两不同。其中对于每个 $i$（$0\\le i\\lt\\ell$），单元格 $(r_i, c_i)$ 和 $(r_{i+1}, c_{i+1})$ 是相邻的。\n\n注意长度为 $\\ell$ 的路径正好包含 $\\ell+1$ 个单元格。\n\n在比赛中，研究人员设置了一个迷宫，其中至少有一条从单元格 $(0,0)$ 到单元格 $(H-1, W-1)$ 的路径。注意，这意味着单元格 $(0, 0)$ 和 $(H-1, W-1)$ 保证为空。\n\nHanga 不知道迷宫中哪些单元格是空的，哪些单元格是障碍。\n\n你的任务是帮助 Hanga 对 Pulibot 进行编程，使其能够在研究人员设置的未知迷宫中找到从单元格 $(0,0)$ 到单元格 $(H-1, W-1)$ 的**最短路径**（即长度最小的路径）。\nPulibot 的说明和比赛规则如下所述。 \n\n注意，在题面的最后一部分描述了一个显示工具，该工具可以用于可视化 Pulibot。\n\n### Pulibot 说明\n\n对每个单元格 $(r,c)$（$-1 \\le r \\le H$ ，$-1 \\le c \\le W$），其**状态**定义为一个整数，具体如下：\n* 如果单元格 $(r,c)$ 是边界，则其状态为 $-2$；\n* 如果单元格 $(r,c)$ 是障碍，则其状态为 $-1$；\n* 如果单元格 $(r,c)$ 是空的，那么它的状态就是单元格的颜色。\n\nPulibot 的程序是按一系列步骤执行的。在每一步中，Pulibot 都会识别附近单元格的状态，然后执行一条指令。它执行的指令由识别的状态决定。以下是更准确的描述。\n\n假设在当前步骤开始时，Pulibot位于单元格 $(r,c)$，这是一个空单元格。该步骤执行如下：\n\n1. 首先，Pulibot 识别当前**状态数组**，即数组 $S = [S[0], S[1], S[2], S[3], S[4]]$， 它包含单元格 $(r,c)$ 及其所有相邻单元格的状态：\n    * $S[0]$ 表示单元格 $(r,c)$ 的状态。\n    * $S[1]$ 表示西邻的状态。\n    * $S[2]$ 表示南邻的状态。\n    * $S[3]$ 表示东邻的状态。\n    * $S[4]$ 表示北邻的状态。\n1. 然后，Pulibot 确定与所识别的状态数组相对应的**指令** $(Z, A)$。\n1. 最后，Pulibot 执行这条指令：它将单元格 $(r,c)$ 的颜色设置为 $Z$，然后它执行动作 $A$, $A$ 是以下动作之一：\n    * **停留** 在单元格 $(r,c)$；\n    * **移动** 到 $4$ 个邻居之一；\n    * **终止程序**。\n\n例如，考虑下图左侧显示的场景。Pulibot 当前位于单元格$(0,0)$，颜色为$0$。\nPulibot 识别出状态数组 $S=[0, -2, 2, 2, -2]$。Pulibot 可能有一个程序，该程序根据所识别的数组，将当前单元格的颜色设置为 $Z=1$，然后向东移动，如图的中间和右侧所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/pg2mek5q.png)\n\n### 机器人比赛规则\n\n* 在开始时，Pulibot 被放置在单元格 $(0,0)$ 并开始执行其程序。\n* 不允许 Pulibot 移动到非空单元格。\n* Pulibot 的程序必须在最多 $500\\,000$ 步后终止。\n* 在 Pulibot 的程序终止后，迷宫中的空单元格的着色满足以下要求：\n  - 存在从 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径，路径中包括的每个单元格的颜色为 $1$。\n  - 所有其他空单元格的颜色为 $0$。\n* Pulibot 可以在任何空单元格终止其程序。 \n  \n\n例如，下图显示了一个可能的迷宫，其中$H=W=6$。左侧显示了初始配置，右侧显示了程序终止后空单元格的一种可以接受的着色：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ry81lf6s.png)"},{"iden":"input","content":"你要实现以下函数：\n\n```\nvoid program_pulibot()\n```\n\n* 这个函数应该产生 Pulibot 的程序。对于所有 $H$ 和 $W$ 的取值以及满足题目约束条件的任何迷宫，该程序应该都能正确工作。\n* 对于每个测试用例，此函数只调用一次。\n\n此函数可以调用以下函数来生成 Pulibot 的程序：\n\n```\nvoid set_instruction(int[] S, int Z, char A)\n```\n\n* $S$: 长度为 $5$ 的数组，用来描述状态数组\n* $Z$: 表示颜色的非负整数\n* $A$: 表示 Pulibot 动作的单个字符，具体如下:\n    - `H`: 停留;\n    - `W`: 移动到西邻;\n    - `S`: 移动到南邻;\n    - `E`: 移动到东邻;\n    - `N`: 移动到北邻;\n    - `T`: 终止程序。\n* 调用此函数指示 Pulibot 在识别状态数组 $S$ 时应执行指令 $(Z, A)$。  \n\n用相同的状态数组 $S$ 多次调用该函数将导致  `Output isn't correct` 的判定结果。\n\n不需要对每个可能的状态数组 $S$ 调用 `set_instruction`。 但是，如果 Pulibot 后来识别出未设置指令的状态数组，你将得到 `Output isn't correct` 的判定结果。\n\n`program_pulibot` 完成后，评测程序会在一个或多个迷宫上调用 Pulibot 的程序。\n这些调用**不**计入解决方案的时间限制。\n评测程序**不**是自适应的，也就是说，每个测试用例的迷宫集合都是预先确定的。\n\n如果 Pulibot 在终止程序之前违反了任何机器人比赛规则，你将得到 `Output isn't correct` 的判定结果。"},{"iden":"output","content":"函数 `program_pulibot` 可以调用 `set_instruction` 如下：\n\n调用                             | 对应状态数组 $S$ 的指令\n:-------------------------------------------:|:---------------------------------------:\n`set_instruction([0, -2, -1, 0, -2], 1, E)`  | 着色 $1$ 并且东移\n`set_instruction([0, 1, -1, 0, -2], 1, E)`   | 着色 $1$ 并且东移\n`set_instruction([0, 1, 0, -2, -2], 1, S)`   | 着色 $1$ 并且南移\n`set_instruction([0, -1, -2, -2, 1], 1, T)`  | 着色 $1$ 并且终止程序\n\n考虑一个场景，$H=2$， $W=3$，迷宫如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/q5lifqvx.png)\n\n对于这个特定的迷宫，Pulibot 的程序分四个步骤运行。 Pulibot 识别的状态数组和它执行的指令正好依次对应上述对“set_instruction”的四次调用。 这些指令的最后一条指令终止程序。\n\n下图展示了四个步骤每一步之前的迷宫以及终止后的最终颜色。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/n236hrg7.png)\n\n但是，注意这个由 $4$ 条指令构成的程序有可能在其他合法的迷宫中找不到最短路径。\n所以，如果这个程序被提交，它会收到 `Output isn't correct` 的判定结果。"},{"iden":"note","content":"## 约束条件\n\n$Z_{\\text{MAX}} = 19$。因此，Pulibot 可以使用 0 到 19 的颜色，包含 0 和 19。\n\n对于每个用来测试Pulibot的迷宫：\n* $2 \\le H, W \\le 15$\n* 至少有一条从单元格 $(0,0)$ 到 $(H-1, W-1)$ 的路径。\n\n## 子任务\n\n1. （6 分）迷宫中没有障碍单元格。\n1. （10 分）$H = 2$\n1. （18 分）任意两个空单元格之间恰好有一条路径。\n1. （20 分）从单元格 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径的长度为 $H + W - 2$。\n1. （46 分）无额外约束条件。\n\n如果在任何测试用例中，对函数 `set_instruction` 的调用或 Pulibot 程序的执行不符合“实现细节”中所描述的限制条件，则该子任务的解决方案得分将为 $0$。\n\n在每个子任务中，你可以通过生成几乎正确的着色来获得部分分数。\n\n形式化地说：\n\n* 如果空单元格的最终颜色满足机器人竞赛规则，则测试用例的解决方案是**完整**的。\n* 如果最终着色如下所示，则测试用例的解决方案是**部分**的：\n   - 存在一条从 $(0,0)$ 到 $(H-1, W-1)$ 的最短路径，路径中包含的每个单元格的颜色为 $1$。\n   - 网格中没有其他颜色为 $1$ 的空单元格。\n   - 网格中的某些空单元格的颜色既不是 $0$ 也不是 $1$。\n   \n\n如果你对某个测试用例的解决方案既不完整也不部分，则该测试用例的得分将为 $0$。\n\n在子任务 1-4 中，对每个测试用例来说，完整解决方案的计分为该子任务分数的 100%，部分解决方案的计分为该子任务分数的 50%。\n\n在子任务 5 中，你的分数取决于 Pulibot 程序中所使用颜色的数量。\n更准确地说，用 $Z^\\star$ 表示对 `set_instruction` 进行的所有调用中 $Z$ 的最大值。\n测试用例上的得分按下表计算：\n\n| 条件            | 分数 (完整)      | 分数 (部分)       |\n|:-----------------------:|:---------------------:|:---------------------:|\n| $11 \\le Z^\\star \\le 19$ | $20 + (19 - Z^\\star)$ | $12 + (19 - Z^\\star)$ |\n| $Z^\\star = 10$          | $31$                  | $23$                  |\n| $Z^\\star = 9$           | $34$                  | $26$                  |\n| $Z^\\star = 8$           | $38$                  | $29$                  |\n| $Z^\\star = 7$           | $42$                  | $32$                  |\n| $Z^\\star \\le 6$         | $46$                  | $36$                  |\n\n\n每个子任务的得分是该子任务中所有测试用例上计分的最小值。\n\n## 评测程序示例\n\n评测程序示例按照以下格式读取输入：\n* 第 $1$ 行: $H \\; W$\n* 第 $2 + r$ 行 ($0 \\le r \\lt H$): $m[r][0] \\; m[r][1] \\; \\ldots \\; m[r][W-1]$\n\n其中，$m$ 是一个 $H$ 行 $W$ 列的二维整数数组，描述迷宫中非边界单元格。\n如果单元格 $(r, c)$ 是空的，$m[r][c] = 0$；如果单元格 $(r, c)$ 是障碍， $m[r][c] = 1$。\n\n\n\n评测程序示例首先调用 `program_pulibot()`。如果评测程序示例检测到违反规则的行为，则会打印 `Protocol Violation: <MSG>` 并终止，其中 `<MSG>` 是以下错误消息之一：\n\n* `Invalid array`：$-2 \\le S[i] \\le Z_{\\text{MAX}}$ 对某些 $i$ 不成立或者 $S$ 的长度不是 $5$。\n* `Invalid color`：$0 \\le Z \\le Z_{\\text{MAX}}$ 不成立。\n* `Invalid action`：字符 $A$ 不是 `H`, `W`, `S`, `E`, `N` 或 `T`。\n* `Same state array`：用相同的 $S$ 调用 `set_instruction` 两次或以上。\n\n否则，当 `program_pulibot` 完成时，评测程序示例将在输入所描述的迷宫中执行 Pulibot 的程序。\n\n评测程序示例产生两个输出。首先，评测程序示例将 Pulibot 动作记录写入工作目录中的文件 `robot.bin` 。\n该文件用作下一节中描述的可视化工具的输入。\n\n其次，如果 Pulibot 的程序未成功终止，评测程序示例将打印以下错误消息之一：\n\n* `Unexpected state`：Pulibot 识别出一个无法调用“set_instruction”的状态数组。\n* `Invalid move`：执行一个动作，导致 Pulibot 移动到一个非空单元格。\n* `Too many steps`：Pulibot 执行了 $500\\,000$ 步没有终止程序。\n\n否则，令 $e[r][c]$ 为 Pulibot 程序终止后单元格 $(r, c)$ 的状态。\n评测程序示例按以下格式打印 $H$ 行：\n* 第 $1 + r$ 行 ($0 \\le r \\lt H$)：$e[r][0] \\; e[r][1] \\; \\ldots \\; e[r][W-1]$\n\n## 显示工具\n\n此任务的附件包含有一个名为 `display.py` 的文件。\n调用时，此 Python 脚本会显示 Pulibot 在由评测程序示例的输入所描述的迷宫中的操作。\n为此，工作目录中要有二进制文件 `robot.bin`。\n\n要调用该脚本，请执行以下命令。\n\n```\npython3 display.py\n```\n\n一个简单的图形界面将会出现，主要特性如下：\n\n* 你可以观察整个迷宫的状态。 Pulibot 的当前位置以矩形突出显示。\n* 你可以通过单击箭头按钮或按热键来浏览 Pulibot 的步骤。 你还可以跳转到特定步骤。\n* Pulibot 程序中即将进行的步骤显示在底部。\n它显示当前状态数组及将要执行的指令。\n在最后一步之后，它或者会显示评测程序的错误消息之一，或者在程序成功终止时显示 `Terminated`。\n* 对于代表颜色的每个数字，你可以指定视觉背景颜色以及显示的文本。 显示的文本是一个短字符串，应出现在每个具有那个颜色的单元格。你可以通过以下任一方式指定背景颜色和显示的文本：\n   - 单击 `Colors` 按钮后在对话框窗口中设置它们。\n   - 编辑 `colors.txt` 文件的内容。\n* 要重新加载 `robot.bin`，请使用 `Reload` 按钮。 这可以用来处理 `robot.bin` 的内容发生更改的情况。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}