《算法竞赛宝典》基础算法艺术(公开课程)

【题目描述】八数码问题（Puzzle8.cpp/c/pas）POJ 1077

邪狼藏进了一个方阵，它由一个3×3的方阵中的八个数码构成，其中的一个单元是空的，它的周边单元中的数码可以移到该单元中。此问题的任务是找到一个数码移动序列使初始的无序数码转变为一些特殊的排列才可以进入该方阵。假定该问题的目标是把数码从开始状态移动到目标状态，如图所示：

【输入格式】

     三行，每行三个整数，表示方阵的开始状态。

【输出格式】

一个整数，表示最少步数。若在5000步内无解，则输出“－1”。

【输入样例】

1 2 3

8 4 0

7 6 5

【输出样例】

1