百度的一道编程比赛题（老题目了），请教思路
题目描述：八方块移动游戏要求从一个含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。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用C/C++实现。
输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。假定start.txt和goal.txt不会相同。
输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出-1。请在数字输出后再输出一回车换行符。
自测用例：如果输入为：start.txt和goal.txt，则产生的输出应为：
5
如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容，则产生的输出应为：
21
如果用
7 5 2
0 6 3
4 1 8
替换start.txt中的内容，则产生的输出应为：
-1
评分规则：我们将首先使用10组不同的start.txt和goal.txt进行测试，每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；
[解决办法]
不就是传说中的八数码问题么?我前两天还编来着,先用逆序数判断解的奇偶性,对于这个问题逆序为奇数,然后用广度优先搜索,对于判断已经搜索过的状态可以用hash查找的方式.大概就是这样的思路,你给的样例我试了下不过100ms,速度很快的.
一些资料:
http://wolfshow.spaces.live.com/?_c11_blogpart_blogpart=blogview&_c=blogpart&partqs=cat%3d%25e7%25ae%2597%25e6%25b3%2595%25e5%25bf%2583%25e5%25be%2597%25e4%25b8%258e%25e8%25ae%25a8%25e8%25ae%25ba
