调兵遣将

第四道门后是一间骑士厅。厅中央有一个5×5的棋盘，棋盘上有一些马——不是真的马，是银色的数据节点，像国际象棋里的骑士。

"Echo的逻辑训练场。"Nyx说，"她学会排序之后，学会的第二件事是移动——用最少的步数，把骑士调到正确的位置。"

"骑士咋个走？"CC问。

"日字形。"你说，"横两格竖一格，或者竖两格横一格。"

"就像……"CC想了想，"像马蹄印。一步一个印，印出来的路线是弯的。"

"对。"

你开始写。先算当前的乱局——有多少个骑士不在目标位置。然后猜一个步数上限，一层一层尝试。每次移动一个骑士，检查它能不能用日字形走到目标位置。如果当前步数加上"乱局数"超过了猜测值，就退回来。

屏幕上跳出了结果。步数：14。

"十四步。"你说。

"就差一步。"CC说，"十五步就超时了。"

"和我们的时间一样。"Echo说。

"啥子意思？"CC问。

"意思是。"Echo说，"每一步都要算好。多一步，就可能被Zero发现。少一步，就可能找不到路。"

棋盘上的骑士在屏幕上跳跃，十四次之后，所有马都归位。骑士厅的墙壁裂开一道缝隙，露出通往第五层的阶梯。

"走。"你说。

题目描述

$5\times 5$ 的棋盘，每个格子有一个骑士（用数字或字母表示）或为空。目标状态给定。每次可以将一个骑士按日字形（横向2格纵向1格，或横向1格纵向2格）移动。求从初始状态到目标状态的最少步数（保证15步内可达）。

输入格式

5行，每行5个字符表示初始状态。然后5行表示目标状态。

输出格式

最少步数。

输入样例

3 3
111
101
111

输出样例

-1
-1
-1

提示

• IDA*。估价函数 = 不在目标位置的棋子数。
• 每次移动最多改变一个棋子的位置，所以估价可采纳。
• 状态用字符串或康托展开编码。

第五道门后是一片玛雅遗迹。无数彩色方块堆叠成金字塔的形状，有些颜色相同，有些不同。

"Echo的消除游戏。"Nyx说，"她学会移动之后，学会的第二件事——消除。找到连在一起的相同颜色，一起消掉。"

"这像……"CC想了想，"像打雪仗。雪球越大，砸得越狠。"

"对。"