AT_awtf2025heuristic_a Group Commands and Wall Planning

有一个 $N\times N$ 的棋盘。左上角的格子的坐标为 $(0, 0)$，向下走 $i$ 格、向右走 $j$ 格的位置坐标为 $(i, j)$。部分相邻格子之间存在墙壁。 棋盘上有 $K$ 台机器人。第 $k$ 台机器人的初始位置为 $(i_k, j_k)$，目标位置为 $(i_k', j_k')$。高桥君需要操作这些机器人，使所有机器人都到达各自的目标位置。 首先，需要进行以下两项准备： 1. 除了最初存在的墙壁外，可以在任意相邻格子之间再设置墙壁。 2. 将机器人分组。每个机器人属于一个组，同组的机器人可以被同时操作。 这些准备工作必须在第一次操作前完成，之后不能再设置新的墙壁或更改分组。 接下来，可以反复进行以下两种操作来移动机器人： 1. **组命令**：指定一个组和一个方向（上下左右），该组内的所有机器人都尝试向该方向移动一格。如果移动方向上有墙壁或有其他机器人，则无法移动。对于指定组内的机器人，按照指定方向上最靠前的顺序依次移动。例如，若 $(1,0)$ 和 $(2,0)$ 有机器人，指定向上移动时，先按 $i$ 坐标小的顺序移动，$(1,0)$ 的机器人先移动到 $(0,0)$，然后 $(2,0)$ 的机器人移动到刚空出来的 $(1,0)$。 2. **单独命令**：指定一台机器人和一个方向（上下左右），该机器人尝试向该方向移动一格。如果移动方向上有墙壁或有其他机器人，则无法移动。 即使机器人曾到达过目标位置，但如果之后又离开目标位置，则不算到达目标。 最多可以进行 $K N^2$ 次操作。请用尽量少的操作次数，使所有机器人都到达各自的目标位置。

输入通过标准输入按以下格式给出。 > $N$ $K$ $i_0$ $j_0$ $i_0'$ $j_0'$ > $\vdots$ > $i_{K-1}$ $j_{K-1}$ $i_{K-1}'$ $j_{K-1}'$ > $v_{0,0}\ \cdots\ v_{0,N-2}$ > $\vdots$ > $v_{N-1,0}\ \cdots\ v_{N-1,N-2}$ > $h_{0,0}\ \cdots\ h_{0,N-1}$ > $\vdots$ > $h_{N-2,0}\ \cdots\ h_{N-2,N-1}$ - 所有测试点中，$N=30$ 固定。 - $10 \leq K \leq 100$。 - $(i_k, j_k)$ 表示第 $k$ 台机器人的初始位置。 - $(i_k', j_k')$ 表示第 $k$ 台机器人的目标位置。 - 所有初始位置、所有目标位置各自互不相同，但第 $k$ 台机器人的初始位置和第 $k'$ 台机器人的目标位置可能相同。 - $v_{i,0}\ \cdots\ v_{i,N-2}$ 是长度为 $N-1$ 的由 `0` 和 `1` 组成的字符串，第 $j$ 位 $v_{i,j}$ 表示格子 $(i,j)$ 和 $(i,j+1)$ 之间是否有墙壁（`1` 表示有，`0` 表示无）。 - $h_{i,0}\ \cdots\ h_{i,N-1}$ 是长度为 $N$ 的由 `0` 和 `1` 组成的字符串，第 $j$ 位 $h_{i,j}$ 表示格子 $(i,j)$ 和 $(i+1,j)$ 之间是否有墙壁（`1` 表示有，`0` 表示无）。 - 保证所有格子之间互相可达。

首先，输出设置墙壁的信息，格式如下： > $v'_{0,0}\ \cdots\ v'_{0,N-2}$ > $\vdots$ > $v'_{N-1,0}\ \cdots\ v'_{N-1,N-2}$ > $h'_{0,0}\ \cdots\ h'_{0,N-1}$ > $\vdots$ > $h'_{N-2,0}\ \cdots\ h'_{N-2,N-1}$ - $v'_{i,0}\ \cdots\ v'_{i,N-2}$ 是长度为 $N-1$ 的由 `0` 和 `1` 组成的字符串，第 $j$ 位 $v'_{i,j}$ 表示是否在 $(i,j)$ 和 $(i,j+1)$ 之间设置墙壁（`1` 表示设置，`0` 表示不设置）。 - $h'_{i,0}\ \cdots\ h'_{i,N-1}$ 是长度为 $N$ 的由 `0` 和 `1` 组成的字符串，第 $j$ 位 $h'_{i,j}$ 表示是否在 $(i,j)$ 和 $(i+1,j)$ 之间设置墙壁（`1` 表示设置，`0` 表示不设置）。 - 对于最初就有墙壁的位置，输出 `0` 或 `1` 均可。 接下来，输出分组信息，格式如下： > $g_0\ g_1\ \cdots\ g_{K-1}$ - $g_k$ 表示第 $k$ 台机器人所属的组，是 $0$ 到 $K-1$ 之间的整数。若 $g_k = g_{k'}$，则机器人 $k$ 和 $k'$ 属于同一组。 最后，输出操作序列，格式如下： > $a_0\ b_0\ d_0$ > $\vdots$ > $a_{T-1}\ b_{T-1}\ d_{T-1}$ - $a_t$ 表示第 $t$ 步操作的类型，组命令为 `g`，单独命令为 `i`。 - $b_t$ 表示第 $t$ 步操作的目标组号或机器人编号，是 $0$ 到 $K-1$ 之间的整数。如果指定了没有机器人的组，则什么都不发生。 - $d_t$ 表示第 $t$ 步操作的方向，用如下字母表示： - 上：`U` - 下：`D` - 左：`L` - 右：`R` [查看示例](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.html?lang=ja&seed=0&output=sample)

### 得分 记操作次数为 $T$，第 $k$ 台机器人最终位置与目标位置的曼哈顿距离为 $d_k$，则绝对分数为： \[ T + 100 \times \sum_k d_k \] **绝对分数越小越好。** 每个测试点，根据 $\mathrm{round}(10^9 \times \frac{\text{全体选手中最小绝对分数}}{\text{你的绝对分数}})$ 得到**相对评分**，所有测试点的相对评分之和为你的提交得分。 最终排名将在比赛结束后对更多输入进行系统测试后决定。无论是临时测试还是系统测试，如果某些测试点输出不合法或超时，则该测试点的相对评分为 $0$，且在该测试点的“全体选手中最小绝对分数”计算时会被排除。系统测试只针对**最后一次非 CE 的提交**进行，请务必确保最终提交的解答无误。 #### 测试点数量 - 临时测试：50 个 - 系统测试：2000 个，比赛结束后公开 [seeds.txt](https://img.atcoder.jp/awtf2025heuristic/seeds.txt) (sha256=063a84b1c0dc9388b0996eed0bc645529c931c139bee6b8e0e84a4faf3e06c40) #### 关于相对评分系统 无论是临时测试还是系统测试，只有最后一次非 CE 的提交会计入排行榜。每个测试点用于计算相对评分的“全体选手中最小绝对分数”也只考虑排行榜上的最后一次提交。 排行榜上显示的是相对评分，每次新提交都会重新计算相对评分。而在提交列表中显示的分数是所有测试点的绝对分数之和，不显示相对评分。若想了解非最新提交在当前排行榜下的相对评分，需要重新提交。若输出不合法或超时，提交列表中的分数为 $0$，但排行榜上会显示正确测试点的相对评分之和。 #### 关于运行时间 运行时间会有一定波动。系统测试时由于同时运行大量程序，运行时间相比临时测试会增加几个百分点。因此，临界时间的提交在系统测试中可能会 TLE。建议在程序中自行计时并提前终止，或留出充足的运行时间。 ### 输入生成方法 设 $\mathrm{rand}(L, U)$ 表示从 $L$ 到 $U$ 间均匀随机生成一个整数。 #### 机器人的生成 机器人数量 $K$ 由 $K = \mathrm{rand}(10, 100)$ 决定。 初始位置从 $N^2$ 个坐标中随机选 $K$ 个且互不重复。 目标位置同理，从 $N^2$ 个坐标中随机选 $K$ 个且互不重复。 #### 墙壁的生成 墙壁线段数 $W$ 由 $W = \mathrm{rand}(0, 2)$ 决定。 以下过程重复 $W$ 次： 1. 随机决定墙壁的方向（上下左右）。 2. 墙壁长度 $L = \mathrm{rand}(10, 20)$。 3. 竖直墙壁时，起点 $(i, j)$ 由 $i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6)$ 选取。若与已生成的竖直墙壁 $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$ 坐标差的绝对值不超过 $4$，则重新选择方向。 - 向左时，将 $h_{i, j-L+1}, \cdots, h_{i, j}$ 设为 `1`；向右时，将 $h_{i, j}, \cdots, h_{i, j+L-1}$ 设为 `1`。超出棋盘部分忽略。 5. 检查所有格子是否互相可达。若不可达，则重置墙壁，重新进行 $W$ 次循环。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.html?lang=ja)：比本地版性能更高，支持动画显示。 - [本地版](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制文件](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4_windows.zip)：不想配置 Rust 环境可直接使用。 比赛期间，禁止分享可视化结果、解法或讨论相关内容。请注意遵守规则。 由 ChatGPT 4.1 翻译