AT_ahc046_a [AHC046A] Skating with Blocks

有一个由 $N \times N$ 个格子组成的滑冰场。左上角格子的坐标为 $(0,0)$，向下 $i$ 格、向右 $j$ 格的位置坐标为 $(i,j)$。$N \times N$ 格子的外部全部被障碍物包围，无法通过。初始状态下，$N \times N$ 格子内部没有任何障碍物。 你现在位于初始位置 $(i_0, j_0)$，需要按顺序依次访问指定的目的地 $(i_1, j_1),\ (i_2, j_2),\ \dots,\ (i_{M-1}, j_{M-1})$。 每一回合，你可以指定一个方向（上下左右），并选择以下三种操作之一执行： - **移动**：向指定方向相邻的格子移动一格。移动目标格子不能有障碍物。 - **滑行**：向指定方向直线滑行，直到撞到障碍物为止。 - **更改**：对指定方向相邻的格子，如果没有障碍物则放置一个障碍物，如果已经有障碍物则移除。不能指定 $N \times N$ 格子的外部。你也可以在当前或未来的目的地上放置障碍物，但那样的话，必须先移除障碍物才能访问该格子。 如果通过“滑行”经过了目的地，并不会视为访问了该格子。只有通过“移动”到达该格子，或“滑行”并在该格子停下，才算访问了目的地。 必须按照指定顺序访问所有目的地。如果提前经过了后面的目的地，并不会视为访问，等到轮到该目的地时还需要重新访问。 最多可以执行 $2NM$ 回合操作。请尽可能用最少的回合数，按顺序访问所有目的地。

输入通过标准输入按以下格式给出。 > $N$ $M$ $i_0$ $j_0$ > $i_1$ $j_1$ > $\vdots$ > $i_{M-1}$ $j_{M-1}$ - 所有测试点中，$N=20$，$M=40$。 - 初始位置和所有目的地的坐标 $(i_k, j_k)$ 满足 $0 \leq i_k, j_k \leq N-1$，且两两不同。

每一回合选择的操作和方向，分别用一个字母表示。 **操作** - 移动：`M` - 滑行：`S` - 更改：`A` **方向** - 上：`U` - 下：`D` - 左：`L` - 右：`R` 第 $t$ 回合（$t=0,1,\dots,T-1$）的操作和方向分别为 $a_t$、$d_t$，请按如下格式输出到标准输出。 > $a_0$ $d_0$ > $a_1$ $d_1$ > $\vdots$ > $a_{T-1}$ $d_{T-1}$

### 得分 设输出的操作序列长度为 $T$，成功访问的目的地数量为 $m$，则得分如下： - 若 $m < M-1$，得分为 $m+1$。 - 若 $m = M-1$，得分为 $M+2NM-T$。 总共有 150 个测试用例，所有测试用例的得分之和为最终提交得分。如果有任意一个测试用例输出不合法或超时，则整份提交判为 WA 或 TLE。比赛期间以最高得分决定最终排名，比赛结束后不进行系统测试。若多名参赛者得分相同，则排名相同，与提交时间无关。 ### 输入生成方法 初始位置和目的地的生成方法如下： 首先将 $N^2$ 个格子的所有坐标随机排列。取排列后的前 $M$ 个，依次作为 $(i_0, j_0), (i_1, j_1), \dots, (i_{M-1}, j_{M-1})$。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc046/EuNd3uow.html?lang=ja)：比本地版性能更高，支持动画显示和手动操作。 - [本地版](https://img.atcoder.jp/ahc046/EuNd3uow.zip)：需要[Rust语言](https://www.rust-lang.org/ja)编译环境。 - [Windows 版编译好的二进制文件](https://img.atcoder.jp/ahc046/EuNd3uow_windows.zip)：如果不方便搭建 Rust 环境可使用此版本。 比赛期间禁止分享可视化结果、讨论解法或思路。请注意遵守规则。 由 ChatGPT 4.1 翻译