总结leetcode75中的图广度优先搜索算法题解题思路。
上一篇：力扣75——图深度优先搜索
1 迷宫中离入口最近的出口
题目：
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）
和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，
你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze
边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
题解：
广度优先搜索。
将与入口相邻的空格子压入队列。
然后用while循环遍历队列中的格子，每个访问过的格子都要做标记（记录它到入口的距离，并将状态设置为已访问）。
如果当前格子为出口，则返回距离d+1。
如果访问玩所有格子，则返回-1。
class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size();
int n = maze[0].size();
// 上下左右四个相邻坐标对应的行列变化量
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
queue<tuple<int, int, int>> q;
// 入口加入队列并修改为墙
q.emplace(entrance[0], entrance[1], 0);
maze[entrance[0]][entrance[1]] = '+';
while (!q.empty()){
auto [cx, cy, d] = q.front();
q.pop();
// 遍历四个方向相邻坐标
for (int k = 0; k < 4; ++k){
int nx = cx + dx[k];
int ny = cy + dy[k];
// 新坐标合法且不为墙
if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.'){
if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1){
// 新坐标为出口，返回距离作为答案
return d + 1;
}
// 新坐标为空格子且不为出口，修改为墙并加入队列
maze[nx][ny] = '+';
q.emplace(nx, ny, d + 1);
}
}
}
// 不存在到出口的路径，返回 -1
return -1;
}
};
2 腐烂的橘子
题目：
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
题解：
广度优先搜索。
定义矩阵dis，记录每个橘子是从第几天开始腐烂的。-1表示未腐烂或者没有橘子。
先找出所有腐烂的橘子，并将其位置存入队列Q。while遍历Q中的烂橘子，如果烂橘子grid[i][j]的周围有未腐烂的橘子，则将对应的dis值改为dis[i][j]+1，并将该橘子的位置压入队列Q。
Q为空之后，查看是否全部腐烂。文章来源：https://www.toymoban.com/news/detail-654682.html
class Solution {
int cnt;
int dis[10][10];
int dir_x[4]={0, 1, 0, -1};
int dir_y[4]={1, 0, -1, 0};
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<pair<int,int> >Q;
memset(dis, -1, sizeof(dis));
cnt = 0;
int n=(int)grid.size(), m=(int)grid[0].size(), ans = 0;
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j){
if (grid[i][j] == 2){
Q.push(make_pair(i, j));
dis[i][j] = 0;
}
else if (grid[i][j] == 1) cnt += 1;
}
}
while (!Q.empty()){
pair<int,int> x = Q.front();Q.pop();
for (int i = 0; i < 4; ++i){
int tx = x.first + dir_x[i];
int ty = x.second + dir_y[i];
if (tx < 0|| tx >= n || ty < 0|| ty >= m|| dis[tx][ty]!=-1 || !grid[tx][ty]) continue;
dis[tx][ty] = dis[x.first][x.second] + 1;
Q.push(make_pair(tx, ty));
cnt -= 1;
ans = dis[tx][ty];
if (!cnt) break;
}
}
return cnt ? -1 : ans;
}
};
1-2 解题总结
题目共同的特点：从起始节点出发，搜索并记录某个或全部节点到起始节点的距离。
是否能用深度优先搜索：不能，因为有些节点可以通过多条路径到达起始节点，如果用深度优先搜索，不能保证某条深度搜索路径算出来的距离是该节点的最短距离。文章来源地址https://www.toymoban.com/news/detail-654682.html
到了这里，关于力扣75——图广度优先搜索的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
