← 返回题目列表

Codeforces · 472/E

E. 设计教程:从游戏中学习

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

创建任务的一种方法是从游戏中学习。你应该选择一个游戏并专注于该游戏的部分机制,那么这可能是一个很好的任务。

我们来尝试一下。 《Puzzle and Dragon》是一款在日本很受欢迎的游戏,我们重点关注该游戏的谜题部分,它是一款瓷砖匹配谜题。

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

有一个由球体组成的 n × m 板。在游戏过程中你可以做以下动作。移动一开始你触摸棋盘上的一个格子,然后你可以将手指移动到相邻的格子之一(不在边界上的格子有8个相邻的格子),然后你可以将手指从当前格子再次移动到相邻的格子之一,以此类推。每次您将手指从一个单元格移动到另一个单元格时,这些单元格中的球体就会相互交换。换句话说,无论你做什么动作,你所触摸的细胞中的球体都不会改变。

目标是实现球体被取消并且你的怪物攻击敌人的模式,但我们不关心这些细节。相反,我们将为您提供初始板作为输入,目标板作为输出。你的目标是确定是否有办法一步一步达到目标。

输入

第一行包含两个整数:n 和 m (1 ≤ n, m ≤ 30)。

接下来的 n 行每行包含 m 个整数——初始棋盘的描述。第 i 行中的第 j 个整数为 si, j (1 ≤ si, j ≤ 900),其中 si, j 表示位于棋盘第 i 行第 j 列的球体的类型。

接下来的 n 行包含相同格式的目标板。请注意,初始板和目标板会有所不同。

输出

如果无解,则输出:-1。

如果有解,则在第一行输出一个整数 k (1 ≤ k ≤ 106) — 手指移动的次数。

在下一行中打印两个整数 x0 和 y0 (1 ≤ x0 ≤ n; 1 ≤ y0 ≤ m) — 您在开始时触摸的单元格的位置。在接下来的 k 行中,每一行打印两个整数 xi 和 yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) — 您移动到的位置。注意,这个位置必须与前一个位置相邻,即 max(|xi - xi - 1|, |yi - yi - 1|) = 1。

如果有多个解决方案,您可以打印其中任何一个。我们可以证明,在这些约束下,如果存在解,则存在不超过 106 次操作的解。

示例

输入 #1

2 2
1 3
2 3
1 3
3 2

输出 #1

3
1 1
2 2
2 1
1 1

输入 #2

2 2
1 3
2 3
1 2
2 3

输出 #2

-1

输入 #3

1 4
1 2 3 4
4 3 2 1

输出 #3

-1

输入#4

4 1
1
2
3
4
3
1
2
4

输出#4

2
3 1
2 1
1 1