八数码难题
提交数: 616, 通过率: 25.16%, 平均分: 46.65
题目描述:
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入格式:
包含六行,每行三个数字,数字之间用空格间隔。前三行为初始状态,后三行为目标状态。
输出格式:
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数。如果无法从初始状态得到目标状态,或移动步数超过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步内不能达到目标状态;
空间限制: 128MB