经典的网格寻路问题实例分析

经典的网格寻路问题

消除墙砖这一设置会导致地形发生变化，增加问题处理的难度。让我们先去掉这一要求，这样题目就简化成了经典的网格寻路问题：

给你一个 的网格，其中每个单元格不是 （空）就是 （障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
请找出从左上角 到右下角 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 。

广度优先搜索算法

我们可以使用广度优先搜索算法来求解经典的网格寻路问题，该算法的思想是：从网格中的起点出发，先访问完所有到起点距离为 1 的点，再去访问到起点距离为 2 的点，以此类推，直到访问到终点位置。这样可以保证从起点到终点的路径是最短的。

我们可以使用队列来实现广度优先搜索算法：首先将起点插入队列，然后循环的从队列首部取出一个点作为当前访问点，并将当前访问点的各个邻居点依次插入到队列的尾部，直到遇到终点或是队列为空。此外，我们还需要记录已经被访问过的点，以免算法陷入死循环。

# 广度优先搜索算法伪代码 queue = Queue() queue.put(start) while queue not empty: cur = queue.get() if cur == end: break for node in cur.neighbors(): if IsInGrid(node) and not IsVisited(node): queue.put(node) MarkVisited(node)

下面看一下算法的运行过程：

网格中的黑色区域表示墙，红色区域表示已经访问过的点，队列中的数字表示当前点到起点的距离。为了记录最短路径，我们可以在网格中标记每个点的前驱点位置（这里用箭头表示），当找到终点后，只需要从终点位置，沿着标记的方向回溯到起点即可。

观察动画可以发现，广度优先搜索算法在访问了网格中的所有点之后，才找到最短路径。这种搜索效率似乎并不高，那么有没有优化的空间呢？