八数码难题
提交数: 609, 通过率: 24.47%, 平均分: 46.21
题目描述:
在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