AT_ahc052_a.[AHC052A] Single Controller Multiple Robots

有一个 $N \times N$ 的网格代表一个办公室。左上角格子的坐标为 $(0, 0)$，第 $i$ 行向下、第 $j$ 列向右的格子的坐标为 $(i, j)$。$N \times N$ 网格的边界被墙包围，相邻格子之间也可能有墙。

你需要使用 $M$ 个机器人对所有格子进行打蜡。第 $k$ 个机器人的初始位置为 $(i_k, j_k)$，包括初始位置在内，机器人经过的所有格子都视为已打蜡。

所有机器人通过一个控制器同时操作。该控制器有 $K$ 个按钮，在开始打蜡操作前，你可以为每个按钮-机器人对配置五种可能的动作之一：向四个相邻格子移动（上、下、左、右）或原地不动。当按下某个按钮时，所有机器人会同时执行各自为该按钮分配的动作。不同机器人在同一个按钮下的动作可以不同。例如，可以将控制器配置为“按钮 0 时，机器人 0 向上移动，机器人 1 向下移动”。一旦打蜡开始，按钮分配不能更改。

如果机器人尝试移动但当前位置与目标格子之间有墙，则机器人保持原地不动。机器人之间不会相互干扰，多个机器人可以占据同一个格子。

你最多可以进行 $2N^2$ 次操作。请设计按钮分配和操作序列，使所有格子都被打蜡，并尽量减少操作次数。

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $i_0$ $j_0$ $⋮$ $i_{M-1}$ $j_{M-1}$ $v_{0,0} \cdots v_{0,N-2}$ $⋮$ $v_{N-1,0} \cdots v_{N-1,N-2}$ $h_{0,0} \cdots h_{0,N-1}$ $⋮$ $h_{N-2,0} \cdots h_{N-2,N-1}$

• 所有测试点中，$N=30$，$M=10$，$K=10$。
• $(i_k, j_k)$ 表示第 $k$ 个机器人的初始位置，所有初始位置互不相同。
• 每一行 $v_{i,0} \cdots v_{i,N-2}$ 是长度为 $N-1$ 的二进制字符串。第 $j$ 个字符 $v_{i,j}$ 表示格子 $(i, j)$ 与 $(i, j+1)$ 之间是否有墙（1 表示有墙，0 表示无墙）。
• 每一行 $h_{i,0} \cdots h_{i,N-1}$ 是长度为 $N$ 的二进制字符串。第 $j$ 个字符 $h_{i,j}$ 表示格子 $(i, j)$ 与 $(i+1, j)$ 之间是否有墙（1 表示有墙，0 表示无墙）。
• 保证所有格子两两可达。

首先输出按钮分配，格式如下：

$c_{0,0}$ $\cdots$ $c_{0,M-1}$ $⋮$ $c_{K-1,0}$ $\cdots$ $c_{K-1,M-1}$

其中，$c_{i,j}$ 是第 $i$ 个按钮被按下时，第 $j$ 个机器人执行的动作。必须是以下 5 种之一：

• U：向上移动一格
• D：向下移动一格
• L：向左移动一格
• R：向右移动一格
• S：原地不动

然后输出操作序列，格式如下：

$a_0$ $⋮$ $a_{T-1}$

其中，$a_t$ 是 $0$ 到 $K-1$ 之间的整数，表示第 $t$ 回合按下的按钮编号。

评分方式

设 $T$（$T \leq 2N^2$）为输出的操作序列长度，$R$ 为未被打蜡的格子数。你的得分计算如下：

• 若 $R = 0$，得分为 $3N^2 - T$。
• 若 $R > 0$，得分为 $N^2 - R$。

共有 $150$ 个测试点，提交的得分为所有测试点得分之和。如果输出非法或某些测试点超时，整份提交判为 WA 或 TLE，得分为零。比赛期间最高得分计入最终排名，赛后不再有系统测试。若多名选手得分相同，则排名并列，与提交时间无关。

输入生成方式

设 $\mathrm{rand}(L, U)$ 为生成 $L$ 到 $U$ 间均匀随机整数的函数。

$M$ 个机器人的初始位置从 $N^2$ 个格子中均匀随机选取 $M$ 个不同坐标。

墙的生成方法如下，重复 5 次：

1. 随机选择墙的方向：上、下、左、右。
2. 确定墙的长度 $L = \mathrm{rand}(10, 20)$。
3. 对于竖直墙，起点 $(i, j)$ 由 $i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6)$ 决定。
   若选中的 $j$ 与之前生成的竖直墙的 $j$ 距离的绝对值不超过 4，则重新选择方向。
   向上墙，将 $v_{i-L+1, j}, \cdots, v_{i, j}$ 设为 1；向下墙，将 $v_{i, j}, \cdots, v_{i+L-1, j}$ 设为 1。越界部分忽略。
4. 对于水平墙，起点 $(i, j)$ 由 $i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5)$ 决定。
   若选中的 $i$ 与之前生成的水平墙的 $i$ 距离的绝对值不超过 4，则重新选择方向。
   向左墙，将 $h_{i, j-L+1}, \cdots, h_{i, j}$ 设为 1；向右墙，将 $h_{i, j}, \cdots, h_{i, j+L-1}$ 设为 1。越界部分忽略。
5. 生成墙后，检查所有格子是否仍然两两可达。若不可达，撤销本次墙并重新进行 5 次生成。

工具（输入生成器与可视化工具）

• 网页版：功能比本地版更强大，支持动画演示。
• 本地版：需要 Rust 语言的编译环境。
  • Windows 预编译版：如不熟悉 Rust 环境可使用此版本。

请注意，比赛期间禁止分享可视化结果或讨论解题思路。

由 ChatGPT 4.1 翻译