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 自动生成**

### ストーリー たこ焼きが大好きな高橋社長は、たこ焼きを移動させるロボットアームの開発をしている。 二次元グリッドで表現されたたこ焼き器上のいくつかのマスにたこ焼きが置かれている。 ロボットアームを用いて、これらのたこ焼きを指定されたマス集合へ移動させたい。 ロボットアームは複数の指先を持ち、関節と指先を頂点とした木構造で表現される。 一回の操作で、ロボットアーム全体を上下左右に動かす、関節を軸に90度回転させる、指先でたこ焼きを掴む、離す、という操作を同時に行うことが出来る。 操作ターン数が出来るだけ少なくなるようにロボットアームを設計し、操作方法を求めて欲しい。  ### 得点 操作ターン数を $ K $、操作終了時に目的地に存在するたこ焼きの個数を $ M' $ とする。 このとき、以下の絶対スコアが得られる。 **絶対スコアは小さければ小さいほど良い。** - $ M'=M $ の場合、$ K $ - $ M'\