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$ 网格中的。

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

• 网页版工具：支持动画和手动游玩，比本地版功能更强。
• 本地版工具：需要安装 Rust 语言环境。
  • Windows 预编译版：若你不熟悉 Rust，可以使用此工具。

请注意，比赛期间禁止分享可视化结果或者讨论解法与思路。

由 ChatGPT 5 翻译