概念：通过上一节的专栏，我们已经了解了 BFS 的基本思想及操作。今天主要讲如何通过BFS解决八数码问题，八数码有点像小时候玩的拼图游戏，九方格里有一个是空的，通过移动空块周围其他方格来完成拼图游戏，这里我们要计算的是最少移动次数。
思路：图中找最优解比较容易想到BFS(当然也有其他方法)，不过这里用字符数组存储整个图不好判断是否已经完成拼图，因为数组不能直接比较是否相等。那么就用字符串存储，模拟一个 3 * 3 的二维数组。
模拟3 * 3的二维数组：字符串中第n个元素对应在3 * 3的二维数组中的位置，行 = n/3，列 = n%3。
例题：
八数码
在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。
C++代码：
题目来源于Acwing，封面来源于网络。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/162379.html