八数码难题

提交数: 616, 通过率: 25.16%, 平均分: 46.65

题目描述:

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
1499494520305160675.png

输入格式:

包含六行,每行三个数字,数字之间用空格间隔。前三行为初始状态,后三行为目标状态。

输出格式:

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数。如果无法从初始状态得到目标状态,或移动步数超过25还不能得到目标状态,则输出“No solution!”。

样例输入:

2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5

样例输出:

5

提示:

对50%的数据, 移动步数不超过10次;
对其余50%的数据, 需超过10次移动才能达到目标状态,或在25步内不能达到目标状态;

时间限制: 1000ms
空间限制: 128MB