AT_ahc052_a [AHC052A] Single Controller Multiple Robots

AtCoder社の高橋社長は、オフィス環境改善のため、最新式のワックスがけロボットを複数台導入した。 これでオフィスの床がピカピカになると安心したのも束の間、重大な問題が発覚した。 操作に必要なコントローラーをたった一つしか注文していなかったのである。 通常であれば絶望的な状況だが、幸いにもそのコントローラーは高度な「キーコンフィグ」機能を備えていた。 各ボタンに対して、ロボットごとに個別の行動を設定できる高機能な装置である。 高橋社長は、あなたにこの難題の解決を依頼した。 限られた手段を駆使して、オフィス全体の床に効率よくワックスがけを行ってほしい。

有一个 $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 次生成。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc052/ZN1uhrbm.html?lang=zh)：功能比本地版更强大，支持动画演示。 - [本地版](https://img.atcoder.jp/ahc052/ZN1uhrbm.zip)：需要 [Rust 语言](https://www.rust-lang.org/)的编译环境。 - [Windows 预编译版](https://img.atcoder.jp/ahc052/ZN1uhrbm_windows.zip)：如不熟悉 Rust 环境可使用此版本。 请注意，比赛期间禁止分享可视化结果或讨论解题思路。 由 ChatGPT 4.1 翻译