题目大意：九宫格中填有0-8九个数字，0可以与上下左右的数字交换，至少交换多少次才能到达123804765的状态呢？

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

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

【输入格式】

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

【输出格式】

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

【输入样例】

1 2 3

8 4 0

7 6 5

【输出样例】

1

解题思路

求最少步数，基本框架跟普通广搜差不多，但是怎么记录状态呢？（这一步走过没有）

首先，状态至多9!种，因此，可以开一个363000大小的数组存储状态，但是怎么快速查找某个状态是否到过？可以用康拓展开或者哈希表。本代码使用的是哈希表，采用除留余数法，找到存储的位置，如果是空，则可以放下去，否则找到一个空的或者自己为止。

接着，就是解决状态转移，把状态看成一个9位数，某两位数字交换，即该位权值*数字差，可以预处理各个位的权值，这样转换就是O(1)。

然后，我们再看看四个方向，往上的话要在二三行，往下要在一二行，往右要在一二列，往左要在三四列……

最后，处理边界问题，考虑如何结束、输出。

程序实现