AT_masters_qual_a Smoothing by Swaps

有一个 $N \times N$ 的棋盘。棋盘的左上角坐标是 $(0,0)$，从这个位置向下移动 $i$ 格、向右移动 $j$ 格的格子坐标为 $(i,j)$。整个棋盘的边缘是围墙，并且在某些相邻格子之间也可能有墙。两个格子如果紧挨且之间没有墙，我们称它们为「相邻格子」。 每个格子 $(i,j)$ 上都有一个从 $1$ 到 $N^2$ 的不重复数字 $a_{(i,j)}$。高桥君和青木君可以从棋盘上的任意位置开始，进行最多 $4N^2$ 次以下操作： 1. 他们可以在当前格子交换各自的数字。 2. 高桥君可以移动到相邻的无墙格子。 3. 青木君也可以移动到相邻的无墙格子。 这些操作按照 $1 \rightarrow 2 \rightarrow 3$ 的顺序依次进行，并视为一个完整的操作。可以选择在不交换数字的情况下直接移动，或者在交换后不移动。两人也可以同时在同一个格子上。 请合理地设计两人的行动方案，使最终相邻格子上数字的差尽量小。

输入为标准输入，格式如下： > $t$ $N$ $v_{0,0} \cdots v_{0,N-2}$ $\vdots$ $v_{N-1,0} \cdots v_{N-1,N-2}$ $h_{0,0} \cdots h_{0,N-1}$ $\vdots$ $h_{N-2,0} \cdots h_{N-2,N-1}$ $a_{0,0} \cdots a_{0,N-1}$ $\vdots$ $a_{N-1,0} \cdots a_{N-1,N-1}$ - $t$ 表示输入生成方式，为 $0 \leq t \leq 19$ 的整数，详情请参阅相关部分。 - 棋盘大小 $N$ 满足 $10 \leq N \leq 100$。 - $v_{i,0} \cdots v_{i,N-2}$ 是由 `0` 和 `1` 组成的 $N-1$ 个字符的字符串，若 $v_{i,j}=1$ 表示 $(i,j)$ 与 $(i,j+1)$ 之间有墙，$v_{i,j}=0$ 没有墙。 - $h_{i,0} \cdots h_{i,N-1}$ 是一个长度为 $N$ 的字符串，同样由 `0` 和 `1` 组成，$h_{i,j}=1$ 表示 $(i,j)$ 和 $(i+1,j)$ 之间有墙，$h_{i,j}=0$ 无墙。 - 保证所有格子间相互可达。 - $a_{i,j}$ 表示初始状态下格子 $(i,j)$ 上的数字，满足 $1 \leq a_{i,j} \leq N^2$。

首先，选择高桥君的初始位置 $(p_i, p_j)$ 和青木君的初始位置 $(q_i, q_j)$，然后在一行输出这两个位置： > $p_i$ $p_j$ $q_i$ $q_j$ 初始位置可以在棋盘范围内任意选择。 接着，对于每个操作，以如下格式输出一行，共 $k$ 行： > $s$ $d$ $e$ - $s$ 是一个字符，表示是否交换数字，`1` 为交换，`0` 为不交换。 - $d$ 是表示高桥君移动方向的字符：向上、下、左、右分别为 `U` `D` `L` `R`，不移动为 `.`。 - $e$ 是表示青木君移动方向的字符，与高桥君的相同规则。 移动如果导致越过墙壁或操作次数超过 $4N^2$，将会判定为错误（WA）。

为评估最终结果，设所有相邻格子对的集合为 $E$，我们关注相邻格子间数字差异的平方和 $\sum_{u,v \in E} (a_u - a_v)^2$。设初始状态下的平方和为 $D'$，最终状态下为 $D$，得分公式如下： \[ \max\left(1, \mathrm{round}\left(10^6 \times \log_2 \frac{D'}{D}\right)\right) \] 共有 200 个测试用例，每个 $t \in \{0, 1, \cdots, 19\}$ 各 10 个，测试总得分为所有用例得分之和。每个 $t$ 值构成的测试集独立评分，输出格式错误或超时将导致该测试集得分为 0。比赛期间所得最高得分将决定最终排名，无系统测试。相同得分者排名并列。 生成 $a$ 以外输入是固定的，由输入生成种子值模 20 决定，见输入生成器的 `in_fixed/t.txt`。每个 $t$ 值测试用例各 $10$ 个。每个格子的数字 $a_{i,j}$ 是通过随机排列 $1$ 到 $N^2$ 生成的。 ### 工具（输入生成器和得分计算程序） - [源代码](https://img.atcoder.jp/masters-qual/ak2uQT08.zip)：需安装 Rust 编译环境。 - [Windows 二进制文件](https://img.atcoder.jp/masters-qual/ak2uQT08_windows.zip)：不愿配置 Rust 时的替代选择。 注意：比赛期间禁止分享可视化结果或讨论算法和思路。 **本翻译由 AI 自动生成**