创建任务的一种方法是从游戏中学习。你应该选择一个游戏并专注于该游戏的部分机制,那么这可能是一个很好的任务。
我们来尝试一下。 《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