先简要解释一下从任何一个状态到目标状态的移动步数不可能小于所有数字当前位置与目标位置的曼哈顿距离之和
考虑一次移动，只能让一个数字的曼哈顿距离加一或者减一，而目标状态所有数字的曼哈顿距离都是0，所以得证
我们可以用普通的BFS做这道题目，由于边权是1，所以第一次搜索到的时候一定是最优情况
考虑用A*优化这个BFS
用上一篇博客相同的方法可以证明这个A*也满足上一篇博客的那个引理
所以当一个状态第一次被取出的时候，实际代价一定是最小的（因为同一状态估价函数相同，不用考虑估价函数的影响），也就只用考虑一次了，不会出现像上上篇博客说的那个问题