A*

题目大意：在 的棋盘上，摆有八个棋子，每个棋子上标有 至 的某一数字。棋盘中留有一个空格，空格用 来表示。空格周围的棋子可以移到空格中，这样原来的位置就会变成空格。给出一种初始布局和目标布局（为了使题目简单，设目标状态如下），找到一种从初始布局到目标布局最少步骤的移动方法。

    123
    804
    765

函数可以定义为，不在应该在的位置的数字个数。

容易发现 满足以上两个性质，此题可以使用 A*算法求解。

按顺序求一个有向图上从结点 到结点 的所有路径最小的前任意多（不妨设为 ）个。

很容易发现，这个问题很容易转化成用 A*算法解决问题的标准程式。

初始状态为处于结点 ，最终状态为处于结点 ，距离函数为从 到当前结点已经走过的距离，估价函数为从当前结点到结点 至少要走过的距离，也就是当前结点到结点 的最短路。

就这样，我们在预处理的时候反向建图，计算出结点 到所有点的最短路，然后将初始状态塞入优先队列，每次取出 最小的一项，计算出其所连结点的信息并将其也塞入队列。当你第 次走到结点 时，也就算出了结点 到结点 的 短路。

由于设计的距离函数和估价函数，每个状态需要存储两个参数，当前结点 和已经走过的距离 。

我们可以在此基础上加一点小优化：由于只需要求出第 短路，所以当我们第 次或以上走到该结点时，直接跳过该状态。因为前面的 次走到这个点的时候肯定能因此构造出 条路径，所以之后再加边更无必要。