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})$。

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

• 网页版：比本地版性能更高，支持动画显示和手动操作。
• 本地版：需要Rust语言编译环境。
  • Windows 版编译好的二进制文件：如果不方便搭建 Rust 环境可使用此版本。

比赛期间禁止分享可视化结果、讨论解法或思路。请注意遵守规则。

由 ChatGPT 4.1 翻译