AT_c_league2026_1_a Polish and Slide

有一个由 $N \times N$ 个格子组成的棋盘。左上角的格子的坐标为 $(0,0)$，向下走 $i$ 格、向右走 $j$ 格的位置坐标为 $(i,j)$。 你现在处于初始位置 $(i_0, j_0)$，需要依次按照指定顺序依次访问目的地 $(i_1, j_1), \dots, (i_{M-1}, j_{M-1})$。 每一回合，你可以选择以下任意一种操作并执行一次： - **擦亮：** 将当前位置的格子擦得锃亮。初始状态下所有格子都是未擦亮的。对已擦亮的格子再次执行该操作不会有任何变化。 - **滑行：** 指定上下左右中的一个方向 $d$，然后重复向该方向移动，直到将要出界或者到达一个未被擦亮的格子为止。具体过程如下： 1. 如果 $d$ 方向上的相邻格子已出界，则停在当前位置结束本次滑行。 2. 如果 $d$ 方向上的相邻格子尚未被擦亮，则移动到该格子并结束本次滑行。 3. 如果 $d$ 方向上的相邻格子已被擦亮，则继续移动到该格子并重复上述过程。  如果在一次「滑行」过程中到达或经过下一个应访问的目的地格子，则视为已访问该目的地。如果在同一次「滑行」动作中按顺序依次经过多个目的地，那么这些目的地都算已被访问。然而，在访问过次序尚未到达的目的地时，并不视为已访问，需要等轮到对应的访问次序时再重新到达或经过此格子。 最多可以进行 $10000$ 回合。请你设计一组行动序列，使得用尽量少的回合数依次访问所有目的地。

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

每一回合的操作用一个字母表示： - **擦亮：** `P` - **滑行：** 按照滑行方向，上：`U`，下：`D`，左：`L`，右：`R` 设回合数为 $T$，第 $t$ 回合操作为 $a_t$，则请按照以下格式输出到标准输出。 > $a_0$ > $\vdots$ > $a_{T-1}$ [查看样例](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.html?lang=ja&seed=0&output=sample)

## 得分 设你的行动序列长度为 $T$，你的得分为 $10000-T$。 如果未能依次访问全部目的地，则本测试点判为 WA。 共有 100 个测试点，你的最终得分为所有测试点得分的总和。如果某一测试点输出格式错误或者用时超限，则整份提交被判为 WA 或 TLE。 ## 输入生成方式 初始位置和每个目的地按照如下流程生成： 首先，将 $N^2$ 个格子的坐标随机打乱。然后从头选取前 $M$ 个，依次作为 $(i_0,j_0),(i_1,j_1),\dots,(i_{M-1},j_{M-1})$。 ## 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.html?lang=ja)：更高性能，支持动画及手动操作。 - [本地版](https://img.atcoder.jp/c-league2026-1/LG9EG0CV.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版已编译可执行文件](https://img.atcoder.jp/c-league2026-1/LG9EG0CV_windows.zip)：如不方便配置 Rust 环境，请使用本版。 比赛期间严禁与队外交流可视化结果或讨论任何解法、思路，请务必注意。 由 ChatGPT 5 翻译