AT_rcl_contest_2020_final_b ハイパーお掃除ロボット

现有一个 $N \times N$ 的网格，第 $i$ 行第 $j$ 列的单元格用 $(i, j)$ 表示。 每个单元格上覆盖着一个纸片，上面写着从 `A` 到 `Z` 一个字母。而网格中的某个单元格内放有一个球形清洁机器人 X，其余 $P$ 个单元格放有柱子。 你的任务是在最多 $M$ 次操作内，通过移动柱子和滚动机器人，帮助机器人收集纸片。具体操作如下： - **移动柱子**：可以将一个柱子移动到另一个空格中，但不能移到有机器人或其它柱子的单元格上。 - **滚动机器人**：可以将机器人向上下左右某个方向滚动。 - 机器人会沿着指定方向一直滚动，直至撞到柱子或网格边界。若撞到柱子，机器人将在该柱子前一格停下；如果没有柱子，机器人则停在网格离边界最近的一个单元格。 - 停止后，若该单元格上有纸片，机器人会立即收集。已收集的纸片若再遇到，则不会再次收集。 一旦所有操作都完成，我们根据机器人收集纸片的顺序来计算一个分数。得分计算规则是：根据收集到的同连续字母的数目计算其平方之和。 （例如：纸片按 `A`, `B`, `B`, `B`, `A`, `B` 顺序收集，分数为 $1^2 + 3^2 + 1^2 + 1^2 = 12$。） 请合理规划移动，从而最大化您的得分。 每个测试用例的分数与总分计算方式如下： - 每个测试用例结束后的分数即为该测试用例的得分。 - 总共有 50 个测试用例，所有测试用例得分之和即为本题的最终得分。

输入格式如下： > $N$ $P$ $M$ $row_{0}$ $\vdots$ $row_{N-1}$ $sheets_{0}$ $\vdots$ $sheets_{N-1}$ - $N$ 是网格的边长，固定为 40。 - $P$ 是柱子的数量，固定为 300。 - $M$ 是可用操作的最大次数，固定为 1000。 - $row_{i}$ 是一个长度为 $N$ 的字符串，其可能字符为 `o`, `x`, `-`。其中： - `o` 表示 $(i, j)$ 处有机器人。 - `x` 表示 $(i, j)$ 处有柱子。 - `-` 表示 $(i, j)$ 处既无机器人又无柱子。 行中保证有且只有一个 `o`，并恰好有 $P$ 个 `x`。 - $sheets_{i}$ 是一个长度为 $N$ 的字符串，每个字符代表 `A` 到 `Z` 间的一个字母，表示对应位置纸片上的字母。

输出最多 $M$ 行，每行表示一次操作： - **移动柱子**：输出 `P`，然后依次输出柱子当前位置 $(r_1, c_1)$ 和目标位置 $(r_2, c_2)$，用空格分隔（$0 \leq r_1, c_1, r_2, c_2 < N$）。若操作非法，即柱子不存在或目标位置有机器人/柱子，会被判为错误。 > P $r_1$ $c_1$ $r_2$ $c_2$ - **滚动机器人**：只需输出一个字符，代表滚动方向，`U`、`D`、`L`、`R` 分别表示向上、下、左、右。 ``` [UDLR] ```

### 测试用例生成说明 测试用例由专门的生成器生成。 可以使用以下链接获取： [生成器、测试器、样例输入数据](https://github.com/recruit-communications/rcl-contest-2020/tree/master/final_B/tester) ### 可视化工具 我们为结果提供了一个可视化工具，通过输入输出计算得分并可视化： - 此工具在最新版本的桌面浏览器 Google Chrome 和 Mozilla Firefox 上已测。其它浏览器不保证正常工作。 - 可视化计算得分与实际比赛得分可能有所不同。最终成绩视 AtCoder 评分结果而定。 - 使用可视化工具导致的任何���失不予负责，请注意风险自担。 可视化工具及说明，可使用下列链接： [可视化工具](https://github.com/recruit-communications/rcl-contest-2020/tree/master/final_B/visualizer) ### 示例解释 这是用于说明的简单示例，不满足所有约束。 程序的操作和说明如下： 初始状态： ``` ---- -o-- x--- -x-- ``` ``` XYZX ZAYX ZBZB XYZX ``` - 机器人从 $(1, 1)$ 向下滚动，会在 $(3, 1)$ 的柱子前一格 $(2, 1)$ 停下，收集一张 `B`： ``` D ``` ``` ---- ---- xo-- -x-- ``` `收集: B` - 继续右滚到边界 $(2, 3)$，收集一张 `B`： ``` R ``` ``` ---- ---- x--o -x-- ``` `收集: BB` - 向左滚动，直到 $(2, 0)$ 的柱子前一格 $(2, 1)$ 停下，此处已收集过，无纸片收集： ``` L ``` ``` ---- ---- xo-- -x-- ``` `收集: BB` - 将 $(2, 0)$ 的柱子移到 $(0, 1)$： ``` P 2 0 0 1 ``` ``` -x-- ---- -o-- -x-- ``` `收集: BB` - 向上滚动，直到 $(0, 1)$ 的柱子前一格 $(1, 1)$ 停止，收集 `A`： ``` U ``` ``` -x-- -o-- ---- -x-- ``` `收集: BBA` 最终得分为 $2^2 + 1^2 = 5$。 **本翻译由 AI 自动生成**