题目描述

本题译自 eJOI2023 Problem D. Square Grid Puzzle

在这个问题中，你将得到一个标号从 $0$ 开始的 $N \times N$ 方格组成的方阵，其中包含从 $0$ 到 $N \times N - 1$ 的不同整数。你的目标是达到有序状态，即对于每个 $0 \leq i, j < N$，第 $i$ 行和第 $j$ 列的交点处的数字都等于 $i \times N + j$。你可以通过两种类型的移动来实现这个目标：

• 下移： "D $a_0\ a_1\ \ldots\ a_{N-1}$"，其中 $a_0\ a_1\ \ldots\ a_{N-1}$ 是网格最上面一行数字的某种重新排列。使用这种移动，最上面的一行将被移除，而由数字 $a_0\ a_1\ \ldots\ a_{N-1}$ 从左到右组成的新行将被添加到网格底部。
• 右移： "R $b_0\ b_1\ \ldots\ b_{N - 1}$"，其中 $b_0\ b_1\ \ldots\ b_{N - 1}$ 是网格最左侧一列数字的某种重新排列。使用这种移动，最左侧的一列将被移除，而由数字 $b_0\ b_1\ \ldots\ b_{N - 1}$ 从上到下组成的新列将被添加到网格右侧。

重新排列是指改变数字的顺序，而不添加或删除任何数字，并且它可能保留原始顺序。

例如，如果当前的网格是：

行/列	0	1	2
0	2	4	6
1	8	1	5
2	7	3	0

通过执行移动 "D 6 2 4"，我们将得到以下网格：

行/列	0	1	2
0	8	1	5
1	7	3	0
2	6	2	4

然而，如果我们执行移动 "R 2 8 7"，我们将得到：

行/列	0	1	2
0	4	6	2
1	1	5	8
2	3	0	7

对于 $N = 3$，目标网格将如下所示：

行/列	0	1	2
0	0	1	2
1	3	4	5
2	6	7	8

你的目标是用少于 $3 \times N$ 次移动来解决这个问题。然而，如果你使用更多的移动或没有解决问题，也可能会获得部分分数。具体详情请参考计分部分。

输入格式

第一行包含一个单独的整数 $N$。

接下来的 $N$ 行每行有 $N$ 个数字，表示初始网格。

输出格式

输出一行一个单独的整数 $M$ 表示移动的次数。接下来的 $M$ 行每行包含一个整数表示一次移动。

计分

令 $M$ 表示你解决方案中的移动次数。此外，令 $A = 3 \times N$ 和 $B = 2 \times N^2$。

如果你的输出不合法，或者 $M > B$，你将获得 $0$ 分。否则，你的分数取决于正确目标位置的数字数量（表示为 $C$）。

如果 $C < N \times N$，问题没有解决，你只会获得 $(50 \times \frac{C}{N\times N})\%$ 的分数。

否则：

• 如果 $M < A$，你将获得测试的 $100\%$ 分数。
• 如果 $A \leq M \leq B$，你将获得 $(40 \times \left(\frac{B-M}{B-A}\right)^2 + 50)\%$ 的分数。

每个测试点都有相同的分数。你的分数是各个测试分数的总和。

3
1 4 2
3 7 5
6 8 0

4
R 3 6 1
D 2 3 4
D 5 6 7
R 2 5 8

样例输出在少于 $9$ 次移动中实现了期望的结果，获得了 $100\%$ 的分数。

2
2 1
0 3

0

问题没有解决，因为只有两个数字（$1$ 和 $3$）在 $4$ 个数字中处于正确的位置。这个输出将获得 $50 \times \frac{2}{4} = 25\%$ 的分数。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 9$
• 没有子任务
• 每个 $N$ 从 $2$ 到 $9$ 都有相同数量的测试点