AT_ahc042_a [AHC042A] Oni wa Soto, Fuku wa Uchi

本日 2月2日、日本では**節分**という伝統行事が行われる。 節分は、季節の変わり目に邪気を払い、福を招くための行事であり、人々は 「鬼は外！」 と唱えながら炒った豆をまいて邪気（鬼）を追い払い、「福は内！」 と唱えながら福を招き入れる。 高橋くんは、そんな節分にちなんだ「鬼は外福は内ボードゲーム」を遊んでいる。 このゲームでも、鬼を追い払い、福を呼び込むことが目的である。 できるだけ高得点を獲得するような手順を求めて欲しい。

有一个由 $N \times N$ 个格子组成的棋盘。最左上角的格子的坐标为 $(0,0)$，从该格子向下走 $i$ 格、向右走 $j$ 格到达的格子的坐标为 $(i,j)$。格子 $(i,0),(i,1),\cdots,(i,N-1)$ 称为**第 $i$ 行**，格子 $(0,j),(1,j),\cdots,(N-1,j)$ 称为**第 $j$ 列**。初始状态下，棋盘上分别有 $2N$ 个**鬼**  和 $2N$ 个**福** ，它们分别位于 $2N$ 个互不相同的格子中。 你每次操作可以选择一行或一列，并将其向左右或上下的某个方向移动一格。 - 将第 $i$ 行向左移动：位于 $(i,0)$ 的棋子会被移出棋盘，对于每个 $j=1,\dots,N-1$，位于 $(i,j)$ 的棋子会移动到 $(i,j-1)$。 - 将第 $i$ 行向右移动：位于 $(i,N-1)$ 的棋子会被移出棋盘，对于每个 $j=0,\dots,N-2$，位于 $(i,j)$ 的棋子会移动到 $(i,j+1)$。 - 将第 $j$ 列向上移动：位于 $(0,j)$ 的棋子会被移出棋盘，对于每个 $i=1,\dots,N-1$，位于 $(i,j)$ 的棋子会移动到 $(i-1,j)$。 - 将第 $j$ 列向下移动：位于 $(N-1,j)$ 的棋子会被移出棋盘，对于每个 $i=0,\dots,N-2$，位于 $(i,j)$ 的棋子会移动到 $(i+1,j)$。 最多可以进行 $4N^2$ 次操作。你的目标是在不移除任何一个福的前提下，用尽可能少的操作次数将棋盘上的所有鬼全部移除。

输入通过标准输入给出，格式如下： > $N$ > $C_0$ > $\vdots$ > $C_{N-1}$ - 棋盘的大小 $N$ 在所有测试用例中均固定为 $N=20$。 - 对于每个 $i=0,1,\cdots,N-1$，$C_i$ 表示第 $i$ 行的初始状态，是一个长度为 $N$ 的字符串，其第 $j$ 个字符含义如下： - `x`：有鬼 - `o`：有福 - `.`：既没有鬼也没有福 - 鬼和福的数量均为 $2N$。 - **对于初始状态下有鬼的每个格子，保证满足以下条件之一。由此保证存在不移除任何福、且在 $4N^2$ 步内移除所有鬼的操作方案。** - 同一列上方所有格子都没有福。 - 同一列下方所有格子都没有福。 - 同一行左侧所有格子都没有福。 - 同一行右侧所有格子都没有福。

将第 $t$ 步操作表示为方向字符 $d_t$ 和行/列编号 $p_t$ 的组 $(d_t, p_t)$： - 将第 $i$ 行向左移动：(`L`, $i$) - 将第 $i$ 行向右移动：(`R`, $i$) - 将第 $j$ 列向上移动：(`U`, $j$) - 将第 $j$ 列向下移动：(`D`, $j$) 按如下格式输出到标准输出： > $d_0$ $p_0$ > $\vdots$ > $d_{T-1}$ $p_{T-1}$ 输出的操作次数 $T$ 必须不超过 $4N^2$。超出上限将被判定为 WA。

## 提示 对于有鬼的格子 $(i,j)$，如果其上方没有福，则连续对第 $j$ 列执行 $i+1$ 次上移操作或 $i+1$ 次下移操作，可以在不移除任何福的情况下移除该鬼。对于下、左、右方向同理。由于这些操作不会改变棋盘上剩余棋子的相对位置，因此对所有鬼都应用上述操作即可在不移除任何福的情况下移除所有鬼。 ## 故事背景 今天是 2 月 2 日，在日本会举行名为**节分**的传统活动。节分是为了在季节更替时驱除邪气、迎接福气的仪式，人们会一边喊着“鬼出去！”一边撒豆驱鬼，同时喊着“福进来！”迎接福气。 高桥君正在玩一款以节分为主题的“鬼出去福进来棋盘游戏”。在这个游戏中，同样需要驱逐鬼、迎接福。 请你设计一个尽可能高分的操作方案。 ## 得分 设输出的操作序列长度为 $T$，最终棋盘上剩余的鬼数为 $X$，被移除的福数为 $Y$，则得分如下： - 若 $X=Y=0$，得分为 $8N^2-T$。 - 若 $X>0$ 或 $Y>0$，得分为 $4N^2-N(X+Y)$。 共有 150 个测试用例，所有测试用例得分之和为提交的总得分。若有任意一个测试用例输出不合法或超时，则整份提交被判为 WA 或 TLE。比赛期间以最高得分计入最终排名，赛后不进行系统测试。若多名参赛者得分相同，则排名并列。 ## 输入生成方法 首先，从 $N^2$ 个格子中随机选出 $2N$ 个不同的格子，放置 $2N$ 个福。 然后，枚举满足以下条件之一的格子，记为 $S$： - 同一列上方所有格子都没有福。 - 同一列下方所有格子都没有福。 - 同一行左侧所有格子都没有福。 - 同一行右侧所有格子都没有福。 若 $S$ 的元素个数小于 $2N$，则重新生成福的位置。 最后，从 $S$ 中随机选出 $2N$ 个格子，放置鬼。 ## 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc042/cnhLtdRT.html?lang=ja)：比本地版功能更强，支持动画和手动操作。 - [本地版](https://img.atcoder.jp/ahc042/cnhLtdRT.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制文件](https://img.atcoder.jp/ahc042/cnhLtdRT_windows.zip)：如不方便搭建 Rust 环境可使用此版本。 比赛期间禁止分享可视化结果、讨论解法或思路。请注意遵守规则。 由 ChatGPT 4.1 翻译