← 返回题目列表

Codeforces · 1044/E

E. 网格排序

中文机器翻译题面 查看原题

给你一个 $$$n \times m$$$ 网格。每个网格单元都填充从 $$$1$$$ 到 $$$nm$$$ 的唯一整数,以便每个整数只出现一次。

在一次操作中,您可以选择网格的任意循环,并将所有整数沿着该循环移动一个空格。这里,循环是满足以下条件的任何序列:

- 至少有四个方块。
- 每个方块最多出现一次。
- 每对相邻的方块以及第一个和最后一个方块共享一条边。

例如,如果我们有以下网格:

我们可以选择一个任意周期,如下所示:

获得以下网格:

在这种特殊情况下,所选的循环可以表示为序列 $$$[1, 2, 3, 6, 5, 8, 7, 4]$$$,数字的方向是我们想要旋转的方向。

找到对网格进行排序的任意操作序列,以便对通过从最高到最低连接行创建的数组进行排序(参见上面的第一张图片)。

请注意,您不需要最小化操作数量或循环长度总和。唯一的限制是所有循环长度的总和不得大于 $$$10^5$$$。我们可以证明在给定的约束下答案总是存在的。输出对网格进行排序的任何有效的移动序列。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n,m \leq 20$$$) — 网格的尺寸。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$x_{i,1}, x_{i,2}, \ldots, x_{i, m}$$$ ($$$1 \leq x_{i,j} \leq nm$$$),表示行 $$$i$$$ 和列中块的值$$$j$$$。

保证所有 $$$x_{i,j}$$$ 都是不同的。

输出

首先,打印单个整数 $$$k$$$,即操作次数 ($$$k \geq 0$$$)。

在接下来的 $$$k$$$ 行中,打印一个循环,如下所示:

$$$$$$s\ y_1\ y_2\ \ldots\ y_s$$$$$$

这里,$$$s$$$ 是要移动的块数 ($$$s \geq 4$$$)。这里,我们将块 $$$y_1$$$ 移动到块 $$$y_2$$$ 所在的位置,块 $$$y_2$$$ 移动到块 $$$y_3$$$ 所在的位置,依此类推,块 $$$y_s$$$ 移动到块 $$$y_1$$$ 所在的位置。

所有操作的 $$$s$$$ 总和最多不得超过 $$$10^5$$$。

示例

输入 #1

3 3
4 1 2
7 6 3
8 5 9

输出 #1

1
8 1 4 7 8 5 6 3 2

输入 #2

3 5
1 2 3 5 10
11 6 4 14 9
12 7 8 13 15

输出 #2

3
4 4 14 13 8
4 5 10 9 4
4 12 7 6 11

注意

第一个样本是语句中的情况。这里,我们可以使用逆序循环来对网格进行排序。