### CEOI2005 解题报告：Depot 问题详解
#### 题目概述
在CEOI2005的比赛中，“Depot”是一个经典的算法问题，它要求通过一系列移动操作，重新排列给定的数列，使得每个长度为M的连续子序列都包含1到M的所有数字。具体来说，题目给出一个由N*M+1个格子组成的序列，其中前N*M个格子里填有数字，而第N*M+1个格子为空。对于每个i (1 ≤ i ≤ M)，确保有N个数字标记为i。任务是通过最少次数的移动操作来重新排列这些数字，使得每个长度为M的连续子序列都包含从1到M的所有数字，并且最后保留第N*M+1个格子为空。
#### 输入格式
- 第一行包含两个整数N和M (1 ≤ N, M ≤ 400)，分别表示每组数字的数量和每组数字的种类数量。
- 第二行包含N*M个整数，代表初始状态下每个格子里的数字。
#### 输出格式
- 第一行输出最小的移动次数S。
- 接下来S行，每行两个整数x和y，表示将数字从第x个格子移动到第y个格子。
#### 示例
**输入示例**
```
5 6
4 1 3 1 6 5 2 3 2 3 5 6 2 1 4 5 6 4 1 3 2 4 5 5 1 2 3 4 6 6
```
**输出示例**
```
8
9 31
18 9
10 18
4 10
3 14
30 31
24 30
31 24
```
#### 解题思路
针对这个问题，本报告提供了两种不同的解决方案，分别由J.Ki和Amber提出。
##### J.Ki的解决方案
J.Ki的方法基于构建二分图的概念。将每个区间[k*M, (k+1)*M] (0 ≤ k ≤ N)作为X岸的一个节点，每个不同的数字作为Y岸的节点。接着，根据每个X岸节点所代表的区间内多出的数字以及该区间内缺少的数字，建立X岸节点与Y岸节点之间的连接。具体来说：
- 将每个X岸节点所代表的区间中多出的数字向Y岸对应数字连接一条边。
- 将每个Y岸节点向代表其空间需求的X岸节点连边。
- 使用类似汉密尔顿路径的算法遍历所有边，如果遍历失败，则另起一点继续遍历剩余的边。
这种方法的核心思想是利用空格进行移动，即始终让空格位于某一个Y岸节点。然后按照特定规则移动空格，使其从一个多余的X岸节点移动到另一个需要该数字的X岸节点。
##### Amber的解决方案
Amber的方法也是基于二分图，但引入了一个更直观的模型来解决问题。将原序列划分为N个长度为M的块，即：
- [1…M]，[M+1…2M]，…，[NM-M+1…NM]。
- 目标是使得每个块都包含所有从1到M的数字。
为此，可以将每个块视为X岸的一个节点，每个数字的“市场”作为Y岸的节点。“市场”可以看作是数字交易的场所，如果某个块中某个数字多出了，则可以将其“卖”给相应的“市场”；反之，如果某个块中某个数字不足，则可以从“市场”中“买”回来。在这个模型下，“买”就是Y向X的一条边，“卖”则是X向Y的一条边。
此外，考虑到M个数字的个数都是N，并且市场不会消耗数字，只是作为一个中转站，因此这实际上构成了一个欧拉图。这意味着问题转化为在二分图上找到欧拉回路，对于所有连通块进行遍历即可得到最优解。
#### 输出方案
关于输出方案，可以通过回溯的方式，仅处理Y岸的节点即可实现路径的输出。这是因为欧拉回路本质上是由一系列循环组成的，因此在回溯过程中可以逆序处理Y岸节点，从而得到最终的操作序列。
无论是J.Ki的方法还是Amber的方法，都是通过构建二分图模型来解决该问题，但具体细节有所不同。这两种方法均能够有效地解决题目要求的问题，提供了一种优雅的算法设计方式。
