经典的网格寻路问题消除墙砖这一设置会导致地形发生变化增加问题处理的难度。让我们先去掉这一要求这样题目就简化成了经典的网格寻路问题给你一个 的网格其中每个单元格不是 空就是 障碍物。每一步您都可以在空白单元格中上、下、左、右移动。请找出从左上角 到右下角 的最短路径并返回通过该路径所需的步数。如果找不到这样的路径则返回 。广度优先搜索算法我们可以使用广度优先搜索算法来求解经典的网格寻路问题该算法的思想是从网格中的起点出发先访问完所有到起点距离为 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)下面看一下算法的运行过程网格中的黑色区域表示墙红色区域表示已经访问过的点队列中的数字表示当前点到起点的距离。为了记录最短路径我们可以在网格中标记每个点的前驱点位置这里用箭头表示当找到终点后只需要从终点位置沿着标记的方向回溯到起点即可。观察动画可以发现广度优先搜索算法在访问了网格中的所有点之后才找到最短路径。这种搜索效率似乎并不高那么有没有优化的空间呢
