算法沉淀——BFS 解决最短路问题（leetcode真题剖析）-慈云数据

在这里插入图片描述

算法沉淀——BFS 解决最短路问题（leetcode真题剖析）

01.迷宫中离入口最近的出口
02.最小基因变化
03.单词接龙
04.为高尔夫比赛砍树
BFS（广度优先搜索）是解决最短路径问题的一种常见算法。在这种情况下，我们通常使用BFS来查找从一个起始点到目标点的最短路径。
具体步骤如下：
1. 初始化：从起始点开始，将其放入队列中，并标记为已访问。
2. BFS遍历：不断从队列中取出顶点，然后探索与该顶点相邻且未被访问的顶点。对于每个相邻顶点，将其标记为已访问，并将其加入队列。这样，每一轮BFS都会探索到当前距离起始点的步数更多的顶点。
3. 重复步骤2：重复这个过程，直到找到目标点或者队列为空。
4. 路径重建（可选）：如果需要找到实际的路径而不仅仅是路径的长度，通常在BFS的过程中维护一个记录每个顶点是由哪个顶点发现的信息，然后通过回溯从目标点追溯到起始点，重建路径。
BFS的优势在于它保证首次到达目标点的路径就是最短路径，因为在BFS的遍历过程中，我们首次访问一个顶点时，它是离起始点最近的未访问顶点之一。

这种算法广泛应用于图的最短路径问题，例如在无权图中寻找最短路径，或者在有权图中，权值为1的情况下寻找最少步数的路径。

01.迷宫中离入口最近的出口

题目链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

示例 1：
```
输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。
```
示例 2：
```
输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。
```
示例 3：
```
输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。
```
提示：
- maze.length == m
- maze[i].length == n
- 1 const int dx[4]={0,0,1,-1}; const int dy[4]={-1,1,0,0}; public: int nearestExit(vector queueentrance[0],entrance[1]}); visit[entrance[0]][entrance[1]]=1; while(!q.empty()){ step++; int sz=q.size(); for(int i=0;i auto [a,b]=q.front(); q.pop(); for(int k=0;k int x=a+dx[k],y=b+dy[k]; if(x=0&&x if(x==0||x==m-1||y==0||y==n-1) return step; q.push({x,y}); visit[x][y]=1; } } } } return -1; } }; public: int minMutation(string startGene, string endGene, vector unordered_set ret++; int sz = q.size(); while (sz--) { string t = q.front(); q.pop(); for (int i = 0; i