AT_ahc059_a [AHC059A] Stack to Match Pairs

有一个 $N \times N$ 的网格。左上角的格子的坐标为 $(0,0)$，从这里向下移动 $i$ 格、向右移动 $j$ 格后到达的格子的坐标为 $(i,j)$。 $N$ 是偶数，对于每一个从 $0$ 到 $\frac{N^2}{2}-1$ 的数字，恰好有两张写有该数字的卡牌。初始时，每个格子上正好放置了一张卡牌。 你从位置 $(0,0)$ 出发，手中持有一个空牌堆，然后重复以下操作： 1. 向上、下、左或右的相邻格子移动。你不能走出 $N \times N$ 的网格范围。 2. 如果你当前位置上有卡牌，则可以将该卡牌放到你牌堆的顶部。如果这之后你牌堆顶端的两张卡牌数字相同，这两张卡牌会被从牌堆中移除。 3. 如果你当前位置上没有卡牌，你可以将牌堆顶端的卡牌放置在当前位置。若你的牌堆为空或当前位置已经有卡牌，则不能执行此操作。 最多可以执行 $2N^3$ 次操作。你的目标是让网格和你的牌堆中所有的卡牌都被消除。请找出一个能够极小化“移动”次数的操作序列。注意，操作 2 和 3 的操作次数计入操作数限制，但并不影响评测分数。

输入通过标准输入给出，格式如下： > $N$ $a_{0,0}$ $\cdots$ $a_{0,N-1}$ $\vdots$ $a_{N-1,0}$ $\cdots$ $a_{N-1,N-1}$ - 所有测试用例均满足 $N = 20$。 - $a_{i,j}$ 表示最初放置在格子 $(i,j)$ 上的卡牌上的数字，是满足 $0 \leq a_{i,j} \leq \frac{N^2}{2} - 1$ 的整数。 - 每个 $a_{i,j}$ 出现恰好两次。

每个回合 $t$ 的操作以单个字符 $c_t$ 表示，含义如下： 1. 操作 1（移动），用如下字符表示方向：向上：“U”、向下：“D”、向左：“L”、向右：“R” 2. 操作 2（拿起卡牌）：`Z` 3. 操作 3（放下卡牌）：`X` 设 $T$ 为总操作次数。请按如下格式输出到标准输出： > $c_0$ > > $\vdots$ > > $c_{T-1}$

### 计分方式 设你的操作序列中移动次数为 $K$，最终网格和牌堆中剩余卡牌数为 $X$，得分计算如下： - 若 $X=0$，得分为 $N^2 + 2N^3 - K$； - 若 $X>0$，得分为 $N^2 - X$。 ### 输入生成 初始的卡牌 $a_{i,j}$ 是将所有 $N^2$ 张卡随机打乱后依次放在 $N \times N$ 网格中的。 ### 工具（输入生成器和可视化） - [网页版工具](https://img.atcoder.jp/ahc059/b8ckwh7N.html?lang=zh-hans)：支持动画和手动游玩，比本地版功能更强。 - [本地版工具](https://img.atcoder.jp/ahc059/b8ckwh7N.zip)：需要安装 [Rust 语言环境](https://www.rust-lang.org/)。 - [Windows 预编译版](https://img.atcoder.jp/ahc059/b8ckwh7N_windows.zip)：若你不熟悉 Rust，可以使用此工具。 请注意，比赛期间禁止分享可视化结果或者讨论解法与思路。 由 ChatGPT 5 翻译