1773. Horses in the chessboard

单点时限: 5.0 sec

内存限制: 256 MB

在一个 5×5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士,且存在一个空位。在任何时候一个骑士都能按照骑士的走法 (走‘日’字) 移动到空位上。

给定一个初始的棋盘和一个目标棋盘,问初始棋盘经过最少的步数移动到目标棋盘。

输入格式

先输入初始棋盘 : 一个 5×5 的矩阵,0 表示白色骑士,1 表示黑色骑士,* 表示空位。

然后输入目标棋盘 : 一个 5×5 的矩阵,0 表示白色骑士,1 表示黑色骑士,* 表示空位。两组数据之间没有空行。

输出格式

对于数据输出一行。如果能在 25 步以内(包括 25 步)到达目标状态,则输出步数,否则输出“Time is not enough!”。

样例

Input
01011
110*1
01110
01010
00100
01011
11001
01110
01*10
00100
Output
1
Hint:
样例中的数据的初始情况对应该图:

0 人解决,2 人已尝试。

0 份提交通过,共有 4 份提交。

9.9 EMB 奖励。

创建: 16 年,6 月前.

修改: 6 年,8 月前.

最后提交: 3 年,5 月前.

来源: LSP

题目标签