| 8数码问题 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 9, Accepted users: 6 |
| Problem 10466 : No special judgement |
| Problem description |
八 方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方 块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移 动。例如，假设一个3x3矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 > 2 0 4 > 0 2 4 > 8 2 4 > 8 2 4 > 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径。
|
| Input |
程序需读入初始状态和目标状态，这两个状态都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。
|
| Output |
如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。
|
| Sample Input |
8 0 3
2 1 4
7 6 5
1 2 3
8 0 4
7 6 5
|
| Sample Output |
5
|
| Problem Source |
| 2005年百度之星程序设计大赛 决赛 |
