迷宫中的最短路径：如何用 BFS 找到最近出口【算法模板】

如何通过广度优先搜索（BFS）求解迷宫问题

在这篇文章中，我们将学习如何使用 广度优先搜索（BFS） 解决一个典型的迷宫问题，具体是从迷宫的一个入口出发，找到最近的出口。我们将一步步分析 BFS 是如何工作的，并展示详细的 C++ 实现代码，帮助你更好地理解算法的原理和细节。

1. 问题描述

假设我们有一个二维迷宫，其中 + 代表墙壁，. 代表空地。迷宫的某些空地可能位于迷宫边缘，作为出口。我们需要找到从迷宫内给定的入口到达最近出口的最短路径。

输入：迷宫矩阵 maze，以及入口坐标 entrance。
输出：从入口到最近出口的步数。如果不存在出口，则返回 -1。

1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

2. 广度优先搜索（BFS）介绍

广度优先搜索 是一种用于搜索树或图的遍历算法，适合用来解决 最短路径问题。BFS 从起始点开始，每次遍历离起始点最近的节点，逐层向外扩展，因此 BFS 保证了找到的第一个解是最短路径。

迷宫问题中的 BFS 思路：

从入口开始进行 BFS，逐步检查四个方向的邻居（上、下、左、右），记录步数。
如果遇到边界上的出口，则返回步数，表示找到最短路径。
如果遍历完整个迷宫没有找到出口，返回 -1。

3. BFS 算法的实现步骤

以下是解题的主要步骤：

初始化数据结构：
- 使用队列（queue）来存储当前要探索的点。
- 使用 visited 数组标记哪些点已经访问过，防止重复访问。
方向数组（directions-vector）：
- 使用一个二维向量 directions，存储四个方向的坐标偏移量，分别代表 上、下、左、右。每次我们检查当前点的四个邻居，看看能否向该方向移动。
BFS 主循环：
- 在 BFS 主循环中，每次从队列中取出当前层的节点，逐步遍历它们的四个邻居。
- 如果某个邻居位于迷宫边界且是空地，我们就找到了出口，返回当前步数。
层次遍历：
- 每当完成一层的遍历，步数 steps 增加。
特殊情况处理：
- 需要确保入口不算作出口，避免错误判断。

4. C++ 代码实现

我们通过 C++ 实现这个 BFS 算法，详细注释解释了每个步骤：

#include <vector>
#include <queue>
using namespace std;class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m = maze.size();    // 行数int n = maze[0].size(); // 列数// 四个方向：上、下、左、右vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 初始化队列和 visited 数组queue<pair<int, int>> q;vector<vector<bool>> visited(m, vector<bool>(n, false));// 将入口加入队列并标记为访问过int startX = entrance[0], startY = entrance[1];q.push({startX, startY});visited[startX][startY] = true;// 记录当前的步数int steps = 0;// 开始 BFSwhile (!q.empty()) {int size = q.size();  // 当前层的节点数量// 遍历当前层的每一个节点for (int i = 0; i < size; ++i) {auto [x, y] = q.front();q.pop();// 检查当前点是否是出口（边界上的空格）if ((x == 0 || x == m - 1 || y == 0 || y == n - 1) && !(x == startX && y == startY)) {return steps;}// 向四个方向扩展for (auto [dx, dy] : directions) {int newX = x + dx;int newY = y + dy;// 检查是否可以移动到新的点if (newX >= 0 && newX < m && newY >= 0 && newY < n && maze[newX][newY] == '.' && !visited[newX][newY]) {q.push({newX, newY});visited[newX][newY] = true;  // 标记为已访问}}}steps++;  // 当前层遍历完后步数增加}return -1;  // 如果遍历完迷宫没有找到出口}
};

5. 代码细节讲解

方向数组（directions）：
- directions 数组包含了四个方向的坐标偏移量：上（{-1, 0}）、下（{1, 0}）、左（{0, -1}）、右（{0, 1}）。这种方法能避免手写多个 if 判断条件，使代码更加简洁。
- 在 BFS 中，遍历当前点的四个邻居时，我们通过这个方向数组，快速获取新的坐标。
队列和层次遍历：
- queue<pair<int, int>> q; 是我们使用的队列，它存储了当前层要探索的坐标。
- 在 BFS 主循环中，每次取出当前层的所有节点，遍历完这一层后步数 steps++。
出口判断：
- 当一个点位于迷宫边界且不是入口时，它就被认为是出口。
时间复杂度和空间复杂度：
- 时间复杂度：由于每个点最多被访问一次，BFS 的时间复杂度为 O(m * n)，其中 m 是迷宫的行数，n 是列数。
- 空间复杂度：BFS 使用了一个 queue 和一个 visited 数组，因此空间复杂度同样是 O(m * n)。

6. 示例分析

我们以几个具体的示例来展示代码的执行过程。

示例 1：

maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]]
entrance = [1,2]

在这里插入图片描述

入口坐标是 (1,2)。
第一次从 (1,2) 开始，向左移动到 (1,1)，向上移动到 (0,2)，而 (0,2) 是一个边界点，符合出口条件。
返回步数 1。

示例 2：

maze = [["+","+","+"],[".",".","."],["+","+","+"]]
entrance = [1,0]

在这里插入图片描述

入口坐标是 (1,0)。
第一次从 (1,0) 开始，向右移动到 (1,1)。
第二次向右移动到 (1,2)，并且 (1,2) 是边界点，返回步数 2。

示例 3：

maze = [[".","+"]]
entrance = [0,0]

在这里插入图片描述

迷宫只有一个空格，且入口本身就是边界，没有其他出口。
因此，返回 -1。

7. BFS 模板总结

BFS 是解决 最短路径问题 的常用算法。常见的 BFS 模板如下：

// 初始化队列和访问数组
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));// 将起点加入队列并标记为访问过
q.push({startX, startY});
visited[startX][startY] = true;// BFS 主循环
while (!q.empty()) {int size = q.size(); // 获取当前层的节点数量// 遍历当前层的每个节点for (int i = 0; i < size; ++i) {auto [x, y] = q.front();q.pop();// 执行某些操作// 向四个方向扩展for (auto [dx, dy] : directions) {int newX = x + dx;int newY = y + dy;// 检查是否可以移动到新的点并继续 BFSif (/* 满足条件 */) {q.push({newX, newY});visited[newX][newY] = true;}}}
}