AT_ahc038_a.[AHC038A] Tree Robot Arm

你需要完成一个任务：在一个 $N \times N$ 的章鱼烧烤盘上移动章鱼烧。网格的左上角坐标为 $(0, 0)$，下移 $i$ 格、右移 $j$ 格后，位置定义为 $(i, j)$。

初始时，有 $M$ 个不同的格子上放置了章鱼烧，目标是将这些章鱼烧移至特定的 $M$ 个目标位置。

首先，你需要设计一个机械臂。这种机械臂用树形结构表示，树的顶点代表"关节"和"指尖"，用刚性线段连接形成一棵树。指尖对应树的叶节点，而关节对应其他节点。用 $L(u, v)$ 表示连接顶点 $u$ 和其子节点 $v$ 的边的长度。

给定机械臂的最大可用顶点数为 $V$，你需要设计一个顶点数不超过 $V$ 的树，并且输出根节点的初始位置。树的每条边的长度 $L(u, v)$ 必须是 $1 \leq L(u, v) \leq N-1$ 的整数。

接着，你需要操作设计好的机械臂来移动章鱼烧。机械臂初始时根节点位于指定位置，所有线段向右伸展。每回合，你可以独立执行以下操作：

1. 整个机械臂可以上下左右移动一格。移动后根节点的坐标 $(x, y)$ 必须满足 $0 \leq x, y \leq N-1$。

2. 对于根节点以外的每一个顶点 $u$，可以以其父结点 $p$ 为基准，对以下的子树整体进行顺时针或逆时针90度旋转。

3. 每个指尖可以独立操作：在当前格子抓取或放下章鱼烧。但不能在已有章鱼烧的格子或者超出 $N \times N$ 范围的格子放置章鱼烧。一个指尖不能同时抓取多个章鱼烧。

操作 2 示例

➡ ➡

如图所示，以顶点 0 为轴将顶点 1 以下的部分树整体顺时针旋转变为中间图。再以顶点 1 为轴将顶点 3 以下的部分树顺时针旋转变为右侧图。

操作的执行顺序是先进行1和2，再进行3。在执行操作3时，要按照顶点编号从小到大的顺序进行(1和2的顺序不影响最终状态)。即便操作后，机械臂的某些部分超出了 $N \times N$ 网格范围，或者多个顶点占用了同一格子，也都是被允许的。

最大可进行 $10^5$ 回合的操作。

输入通过标准输入给定，格式如下：

$N$ $M$ $V$
$s_{0,0}\cdots s_{0,N-1}$
$\vdots$
$s_{N-1,0}\cdots s_{N-1,N-1}$
$t_{0,0}\cdots t_{0,N-1}$
$\vdots$
$t_{N-1,0}\cdots t_{N-1,N-1}$

• $N$ 是网格的大小，范围为 $15 \leq N \leq 30$。
• $M$ 是章鱼烧的数量，范围为 $N^2/10 \leq M \leq N^2/2$。
• $V$ 是可用机械臂的最大顶点数，范围为 $5 \leq V \leq 15$。
• $s_{i,0}\cdots s_{i,N-1}$ 由 '01' 组成的长度 $N$ 的字符串，如果第 $j$ 位为 '1'，表示初始时格子 $(i, j)$ 放置了章鱼烧。总共有 $M$ 个放置章鱼烧的格子。
• $t_{i,0}\cdots t_{i,N-1}$ 也是由 '01' 组成的长度 $N$ 的字符串，如果第 $j$ 位为 '1'，表示格子 $(i, j)$ 是目标位置。共有 $M$ 个目标位置的格子。

输出机械臂的设计和操作序列。

1. 机械臂设计部分：

   • 设机械臂的顶点数为 $V'$（$1 \leq V' \leq V$）。顶点 $0$ 为根，顶点编号为 $0, \cdots, V'-1$。
   • 对于顶点 $u$（$1 \leq u \leq V'-1$），其父节点为 $p_u$（$0 \leq p_u \leq u-1$），边 $(p_u, u)$ 的长度为 $L(p_u, u)$（$1 \leq L(p_u, u) \leq N-1$）。
   • 根节点的初始坐标为 $(x, y)$（$0 \leq x, y \leq N-1$）。

   输出格式：

   $V'$
   $p_1$ $L(p_1, 1)$
   $\vdots$
   $p_{V'-1}$ $L(p_{V'-1}, V'-1)$
   $x$ $y$

2. 操作序列部分：

   • 每一回合的操作用 $2V'$ 个字符的字符串 $S$ 表示。

   • 第 0 位表示整个机械臂的移动：U、D、L、R 分别表示上、下、左、右移动，不移动则为 .。

   • 第 $i$ 位（$1 \leq i \leq V'-1$）表示以 $p_i$ 轴为基进行旋转：逆时针为 L，顺时针为 R，不操作则为 .。

   • 第 $(V'+i)$ 位（$0 \leq i \leq V'-1$）表示指尖操作：抓取或放下章鱼烧为 'P'，不操作或不是指尖则为 .。

   • 设操作序列的总长度为 $T$，第 $t$ 回合的操作用字符串 $S_t$ 描述。输出格式：

   $S_0$
   $\vdots$
   $S_{T-1}$

以上是任务的详细描述，请设计和实现对应的操作序列，完成章鱼烧的移动。

本翻译由 AI 自动生成