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$ 生成的。

工具（输入生成器和得分计算程序）

• 源代码：需安装 Rust 编译环境。
  • Windows 二进制文件：不愿配置 Rust 时的替代选择。

注意：比赛期间禁止分享可视化结果或讨论算法和思路。

本翻译由 AI 自动生成