CF472E.Design Tutorial: Learn from a Game

One way to create task is to learn from game. You should pick a game and focus on part of the mechanic of that game, then it might be a good task.

Let's have a try. Puzzle and Dragon was a popular game in Japan, we focus on the puzzle part of that game, it is a tile-matching puzzle.

(Picture from Wikipedia page: http://en.wikipedia.org/wiki/Puzzle_&_Dragons)

There is an n × m board which consists of orbs. During the game you can do the following move. In the beginning of move you touch a cell of the board, then you can move your finger to one of the adjacent cells (a cell not on the boundary has 8 adjacent cells), then you can move your finger from the current cell to one of the adjacent cells one more time, and so on. Each time you move your finger from a cell to another cell, the orbs in these cells swap with each other. In other words whatever move you make, the orb in the cell you are touching never changes.

The goal is to achieve such kind of pattern that the orbs will be cancelled and your monster will attack the enemy, but we don't care about these details. Instead, we will give you the initial board as an input and the target board as an output. Your goal is to determine whether there is a way to reach the target in a single move.

一种设计任务的方法是向游戏学习。你需要选择一款游戏，并专注于该游戏的某一部分机制，这样就可能形成一个不错的任务。

我们来尝试一下。《智龙迷城》（Puzzle & Dragons）曾是日本的一款热门游戏，我们聚焦于其中的解谜部分——这是一款方块匹配类益智游戏。

（图片来自维基百科页面：http://en.wikipedia.org/wiki/Puzzle_&_Dragons）

游戏有一个 $n \times m$ 的棋盘，其上布满各种“珠子”（orbs）。在游戏过程中，你可以执行如下操作：在一次操作开始时，你触碰棋盘上的某个格子；随后，你可以将手指滑动至与当前格子相邻的一个格子（非边界格子有 8 个相邻格子）；接着，你还可以继续从当前格子滑动至其一个相邻格子，如此反复。每次手指从一个格子滑动到另一个格子时，这两个格子中的珠子便会相互交换。换言之，无论你如何滑动，你手指始终接触的那个格子中的珠子不会改变位置。

游戏目标是达成某种特定图案，从而消除珠子并使你的怪物攻击敌人；但我们不关心这些细节。相反，本题将为你提供初始棋盘状态作为输入、目标棋盘状态作为输出。你的任务是判断：是否存在一种单次滑动操作，使得初始棋盘能恰好变为目标棋盘。

The first line contains two integers: n and m (1 ≤ n, m ≤ 30).

The next n lines each contains m integers — the description of the initial board. The j-th integer in the i-th line is s__i, j (1 ≤ s__i, j ≤ 900), where s__i, j denotes the type of the orb located in the i-th row and j-th column of the board.

The next n lines contain the target board in the same format. Note, that the initial board and the target board will be different.

第一行包含两个整数：$n$ 和 $m$（$1 \leq n, m \leq 30$）。

接下来的 $n$ 行，每行包含 $m$ 个整数——描述初始棋盘。第 $i$ 行中的第 $j$ 个整数为 $s_{i,j}$（$1 \leq s_{i,j} \leq 900$），其中 $s_{i,j}$ 表示位于棋盘第 $i$ 行、第 $j$ 列的法珠类型。

再接下来的 $n$ 行以相同格式给出目标棋盘。注意，初始棋盘与目标棋盘必定不同。

If there is no solution, then output: -1.

If there is a solution, then in the first line output an integer k (1 ≤ k ≤ 106) — the number of finger moves.

In the next line print two integers _x_0 and _y_0 (1 ≤ _x_0 ≤ n; 1 ≤ _y_0 ≤ m) — the position of the cell you touch at the beginning. In each of the next k lines print two integers x__i and y__i (1 ≤ x__i ≤ n; 1 ≤ y__i ≤ m) — the position you move to. Note that this position must be adjacent to the previous position, that is max(|x__i - x__i - 1|, |y__i - y__i - 1|) = 1.

If there are multiple solutions, you can print any of them. We can prove that under these constraints if there exists a solution then there is a solution with no more than 106 operations.

如果无解，则输出：-1。

如果有解，则第一行输出一个整数 $k$（$1 \leq k \leq 10^6$）—— 表示手指移动的次数。

第二行输出两个整数 $x_0$ 和 $y_0$（$1 \leq x_0 \leq n$；$1 \leq y_0 \leq m$）—— 表示初始触摸的格子位置。接下来的 $k$ 行中，每行输出两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \leq n$；$1 \leq y_i \leq m$）—— 表示每次移动到达的位置。注意：该位置必须与上一位置相邻，即满足 $\max(|x_i - x_{i-1}|,\, |y_i - y_{i-1}|) = 1$。

若存在多个解，输出任意一个即可。在本题约束下，我们可以证明：若存在解，则必存在一个操作次数不超过 $10^6$ 的解。