数据结构作业—用队列求解迷宫问题

迷宫问题本质上是一个图的搜索问题。我们可以把迷宫中的每一个可通行的格子看作图中的一个节点，相邻的可通行格子之间存在边。从起点到终点的路径，就是从图中的一个节点出发，沿着边走到另一个节点的过程。在这样一个图结构中，我们需要找到最短路径，也就是途经格子最少的路径。

在此过程中，我们有两种方法可用：广度优先和深度优先。

若采用深度优先，使用栈来实现。效果为选定一个方向一直走到底，走不通再回头尝试其他方向。这种方式能找到一条路径，但不能保证是最短的。

若采用广度优先，使用队列来实现。队列具有先进先出的特性，这意味着先进入队列的节点会先被处理。利用这个特性，我们可以实现按层搜索。首先处理距离起点最近的节点，处理完所有距离为一的节点后，再处理距离为二的节点，以此类推。正因为这种层层推进的方式，当我们第一次到达终点时，所经过的距离一定是最短的。

第一步是初始化阶段。我们需要创建一个空队列，这个队列用来存放待处理的节点。然后把起点放入队列中。同时需要建立一个二维数组用来记录每个位置是否已经被访问过，初始时全部标记为未访问，只把起点标记为已访问。另外还需要一个二维数组用来记录每个节点是从哪个节点走过来的，这个信息在最后重建路径时至关重要。

第二步进入主循环阶段。只要队列不为空，就从队列的头部取出一个节点作为当前正在处理的节点。检查这个当前节点是不是终点，如果是终点，说明搜索成功，跳出循环，进入路径重建阶段。如果不是终点，就需要探索从这个当前节点出发能够到达的所有相邻节点。一般来说可以向上、下、左、右四个方向移动。对于每一个方向的邻居节点，需要做一系列检查。首先检查这个邻居是否在迷宫范围内，如果超出边界就不能走。然后检查这个邻居是不是墙壁，如果是墙壁也不能走。最后检查这个邻居是否已经被访问过，如果已经访问过就跳过，因为从其他路径走到这个节点的距离只会更远或者相等，再次访问没有意义。只有同时满足在迷宫范围内、是通路、且未被访问这三个条件的邻居节点才是有效的。对于每一个有效的邻居节点，首先把它标记为已访问，然后记录它的父节点是当前节点，最后把这个邻居节点放入队列的尾部等待后续处理。

第三步是路径重建阶段。当搜索到达终点后，我们从终点开始，通过之前记录的父节点信息一步步往回追溯。从终点找到它的父节点，再从父节点找到父节点的父节点，一直追溯到起点为止。这个追溯过程得到的序列是从终点到起点的逆序路径。最后把这个序列反转过来，就得到了从起点到终点的正向最短路径。

运行结果如下：

心得总结：迷宫问题看似简单，却蕴含着算法设计中的诸多重要思想。通过队列实现广度优先搜索来求解最短路径，我学习了数据结构选择的重要性，理解了空间与时间的权衡关系，锻炼了问题抽象能力，体会了细节处理的关键性，掌握了系统化的解题思路。这些收获不仅限于这一个算法，而是可以迁移应用到更广泛的问题解决中。算法学习的价值，或许正在于这种思维方式的内化和解决问题能力的提升。

源码：使用队列实现迷宫问题求解
https://gitee.com/gortash66/data-structure-assignment/issues/IIRZBB