更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361885

这个题目要求我们把给出的状态通过类似华容道的方式，去移动 $0$ 的位置，然后就可以调整其他数的位置。

然后我们考虑把这个棋盘的状态存下来，这样的话我们就可以直接转移，然后我们显然可以把这玩意直接弄成字符串，为了保证答案的最小，直接字符串 $hash$ 存每个字符串的最小值，然后我们每次关注 $0$ 的位置，进行 bfs 即可，新的状态取最小即可。这种已经可以 AC了。

我们继续考虑优化，这里给出 A* 的写法，我们是否有很多没必要的状态呢？A* 的剪枝就很类似于贪心的思路，我们可以维护一个东西，每次在 bfs 的时候取你觉得比较优的答案。这时候我们需要维护一个估价函数，对于这个题的话，我们可以认为，位置正确的越多，那么这个东西显然很优，先对这些正确位置比较多的进行拓展，那么我们有 $F(S)$ 就是表示当前的状态下正确的位置的个数，然后我们去维护一个小根堆，里面的值是 $S_{now} + F(S)$，这个东西越小显然越优，我们优先去拓展，如果已经到了目标状态，那么就没必要继续搜索了，这个答案一定最优。这个东西就很类似最短路的 dijkstra，每次都取最小的。然后显然我们的 $F(S)$ 是要小于等于实际的可能花费的，因此这样的拓展一定最优。