【算法深练】BFS：“由近及远”的遍历艺术，广度优先算法题型全解析_格子地图一层一层往外遍历算法
前言
宽度优先遍历BFS与深度优先遍历DFS有本质上的区别，DFS是一直扩到低之后找返回，而BFS是一层层的扩展就像剥洋葱皮一样。
- 通常BFS是将所有路径同时进行尝试，所以BFS找到的第一个满足条件的位置，一定是路径最短的位置，而DFS是将一条路走到底，走完了还不能确定是否是最短的；所以在解决求最短路是BFS效率更高。
- 因为DFS是一条路走到底，所以DFS得到得到一条支路的速度比BFS更快，所以DFS通常可以用来检查某个特定的支路是否存在。
下面通过一个题看看BFS的样子：
此题就是经典的BFS题目，给定一个位置，找出要走多少步才能找到出口：因为是以人为坐标位置一层层的向外进行扩展的，所以可以采用宽度优先遍历，一层层的向外进行扩展知道扩展到出口位置。
深度优先遍历解题步骤：
- 确定起始位置+准备工作(设置队列存放下一步可以走的位置)；
- 找下一个位置，将下一个位置入队列，对已经入队列的位置进行标记；
- 判断下一个位置是否满足条件；
- 进行下一层循环，继续2，3步.
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单
BFS经典题目
1926. 迷宫中离入口最近的出口
就是前言的题目，此处直接贴代码：
class Solution {public: int nearestExit(vector<vector>& maze, vector& entrance) { //使用BFS一层层的向外扩 int n=maze.size(),m=maze[0].size(),step=0; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; queue<pair> st; //记录向外扩的坐标 st.push({entrance[0],entrance[1]}); maze[entrance[0]][entrance[1]]=\'+\'; while(!st.empty()) { //此时st不为空,说明还可以像外扩 int num=st.size(); step++; //先外扩,次数+1 for(int i=0;i<num;i++) { int x=st.front().first,y=st.front().second; st.pop(); for(int k=0;k<4;k++) { int a=x+dx[k],b=y+dy[k]; if(a=n||b=m||maze[a][b]==\'+\') continue; //不满足条件的坐标 if(a==0||a==n-1||b==0||b==m-1) return step; //找到了目标位置 maze[a][b]=\'+\'; //在此处就需要将矩阵坐标置为\'+\'防止其他位置重复加入,导致超时 st.push({a,b}); //将当前位置加入到队列中 } } } return -1; }};1091. 二进制矩阵中的最短路径
此题如果使用DFS会导致已经走过的路径不好处理,如果直接将已经走过的路径禁止掉,就会导致一些更短的路径被裁剪掉，如果不进行裁剪直接遍历全部会超时。所以此题使用BFS会更方便处理一些。
class Solution {public: int shortestPathBinaryMatrix(vector<vector>& grid) { if(grid[0][0]==1) return -1; int n=grid.size(),m=grid[0].size(); int dx[]={0,0,-1,-1,-1,1,1,1}; int dy[]={-1,1,1,-1,0,1,-1,0}; //此题如果使用DFS会导致已经走过的路径不好处理,如果直接将已经走过的路径禁止掉,就会导致一些更短的路径被裁剪掉 //所以此题使用BFS更好 queue<pair> q; vector<vector> vist(n,vector(m)); q.push({0,0}); int ret=0; while(!q.empty()) { ret++; int _size=q.size(); for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; vist[x][y]=1; q.pop(); if(x==n-1&&y==m-1) return ret; for(int k=0;k=0&&a=0&&b<m&&grid[a][b]==0&&!vist[a][b]) { q.push({a,b}); vist[a][b]=1; } } } } return -1; }};1162. 地图分析
与上一题一样，只不过有多个起始位置，需要从多个起始位置出发，找最大的距离。可以枚举每一个位置，在每一个0的位置找最近的路径，再找出路径中的最大值。
class Solution {public: int maxDistance(vector<vector>& grid) { int n=grid.size(),m=grid[0].size(); int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; function bfs=[&](int x1,int y1) //从(x1,y1)开始向周围找最近距离 { vector<vector> vist(n,vector(m)); int step=0; queue<pair> q; q.push({x1,y1}); vist[x1][y1]=1; while(!q.empty()) { step++; int _size=q.size(); for(int z=0;z<_size;z++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b=0&&a=0&&b<m&&!grid[a][b]&&!vist[a][b]) { q.push({a,b}); vist[a][b]=1; } } } } return -1; }; int ret=-1; for(int i=0;i<n;i++) //枚举每一个0的位置开始向周围找陆地 { for(int j=0;j<m;j++) { if(grid[i][j]) continue; ret=max(ret,bfs(i,j)); } } return ret; }};以上枚举时间为O(N^2)，进行BFS的时间为O(N^2)，所以如果根据根据以上写法时间复杂度就是O(N^4)在leetcode上会超时，所以能否将算法进行优化？？？
有多个起点，其终点是距离其最近的陆地。那能不能以陆地为起点，向外进行扩展，如果扩展到水面，那么水面到陆地的距离不久确定了吗。 但是这样不还是要对每个陆地依次进行BFS，能否让所有陆地同时进行BFS，好像确定可以，将所有陆地同时入队列，依次向外进行扩展，当一个水面第一次被扩展到时，该水面到陆地的最短距离就确定了。
以上方法就是将「多源 BFS」问题转换为「单源 BFS」问题 。
图片来自宫水三叶。
class Solution {public: int maxDistance(vector<vector>& grid) { int n=grid.size(); int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; queue<pair> q; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(grid[i][j]==1) q.push({i,j}); //将陆地全部入队列 int ret=-1,step=0; vector<vector> vist(n,vector(n)); while(!q.empty()) //进行BFS { int _size=q.size(); step++; for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b<n&&!grid[a][b]&&!vist[a][b]) { ret=max(ret,step); //更新答案 vist[a][b]=step; //对该位置进行标记 q.push({a,b}); //入队列,为下一次扩展做准备 } } } } return ret; }};542. 01 矩阵
与上一题一样，此题也是一道多源BFS问题，需要转化为单元BFS，可以将0看作起点，依次向外进行扩展，扩展到1位置该位置的答案就确定了。
class Solution {public: vector<vector> updateMatrix(vector<vector>& mat) { //多源BFS,从0开始向外进行扩展 int n=mat.size(),m=mat[0].size(); int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; queue<pair> q; for(int i=0;i<n;i++) //记录所有0位置 for(int j=0;j<m;j++) if(mat[i][j]==0) q.push({i,j}); //进行BFS int step=0; vector<vector> ret(n,vector(m)); while(!q.empty()) //进行BFS { int _size=q.size(); step++; for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b<m&&mat[a][b]&&!ret[a][b]) { ret[a][b]=step; //对该位置答案进行更新 q.push({a,b}); } } } } return ret; }};994. 腐烂的橘子
依旧是采用多源BFS，以每一个已经腐烂的桔子为起点向周围进行扩展，直到所有的桔子都腐烂或者已经不能在扩展为止。
class Solution {public: int orangesRotting(vector<vector>& grid) { //多源BFS问题 int n=grid.size(),m=grid[0].size(); int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; //先将所有腐烂的桔子入队列 queue<pair> q; int fine=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(grid[i][j]==1) fine++; else if(grid[i][j]==2) q.push({i,j}); } } if(fine==0) return 0; //从每个腐烂的桔子位置开始向外进行BFS int step=0; while(!q.empty()) { int _size=q.size(); step++; for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b<m&&grid[a][b]==1) { if(--fine==0) return step; //已经没有好橘子了 grid[a][b]=2; //将改新鲜橘子标记为腐烂 q.push({a,b}); } } } } return -1; }};1765. 地图中的最高点
相邻格子的高度差至多为1,已知水域的高度为0,那不就可以从水域开始向外进行扩展。
细节：必须保证每个陆地的高度都只能被更新一次，进而保证陆地的高度是最矮的，否则可能会出现相邻两个的高度差超过1的情况。
class Solution {public: vector<vector> highestPeak(vector<vector>& isWater) { int n=isWater.size(),m=isWater[0].size(); int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; //相邻格子的高度差至多为1,已知水域的高度为0,那不就可以从水域开始向外进行扩展 queue<pair> q; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(isWater[i][j]==1) { isWater[i][j]=-1; //先将水面置为-1,如果直接将其置为0,就和陆地搞混在一起了 q.push({i,j}); } } } int step=0; while(!q.empty()) { int _size=q.size(); step++; for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b<m&&!isWater[a][b]) { isWater[a][b]=step; //对陆地的高度进行更新,只能更新依次,报站高度差不超过1 q.push({a,b}); } } } } for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(isWater[i][j]==-1) isWater[i][j]=0; //将用-1标记的水面全部置为0 return isWater; }};BFS面试难题剖析
934. 最短的桥
最短的桥，要找到从一座岛到另一座岛需要填多少水域，直接让一座岛向外进行扩展，直到扩展到另一座岛的位置时，停止。使用DFS统计一座岛的所有坐标，使用BFS将一座岛向外进行扩展。
class Solution {public: int shortestBridge(vector<vector>& grid) { //将水面填平,让两座岛形成一座岛 //可以让一座岛向外进行扩展,当从一座岛扩展到另一座岛的时候,其就已经填平了,直接返回扩展的次数即可 int n=grid.size(),m=grid[0].size(); int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; //先分别对两座岛的陆地进行统计 function<void(queue<pair>&,int,int)> dfs=[&](queue<pair>& q,int x,int y) { grid[x][y]=2; //将这个岛置为2,于另一个岛进行区分 q.push({x,y}); for(int k=0;k=0&&a=0&&b<m&&grid[a][b]==1) dfs(q,a,b); } }; queue<pair> q; int flag=1; for(int i=0;i<n&&flag;i++) { for(int j=0;j<m&&flag;j++) { if(grid[i][j]==1) { dfs(q,i,j); flag=0; //通过flag标记来跳出循环 } } } //此时一个岛都已经进行统计了 //让这个岛向外进行扩展,直到扩展到另一个岛 int step=0; //记录已经扩展的次数 while(q.size()) { int _size=q.size(); for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b=0&&a=0&&b<m&&grid[a][b]==0) { grid[a][b]=2; q.push({a,b}); } } } step++; } return -1; }};2146. 价格范围内最高排名的 K 样物品
优先级:距离>价格>横坐标>纵坐标，因为是距离优先,所以考虑BFS,让距离从小到大一次向外扩展。每一次向外扩展时还需要对各个方向的数据进行排序，所以总而言之就是：BFS+排序。
class Solution {public: vector<vector> highestRankedKItems(vector<vector>& grid, vector& pricing, vector& start, int tar) { //优先级:距离>价格>横坐标>纵坐标 //因为是距离优先,所以考虑BFS,让距离从小到大一次向外扩展 int n=grid.size(),m=grid[0].size(); vector<vector> dxy({{0,1},{0,-1},{1,0},{-1,0}}); vector<vector> ret; //返回值 int low=pricing[0],heigh=pricing[1],sx=start[0],sy=start[1]; queue<pair> q; //队列 if(grid[sx][sy]>=low&&grid[sx][sy]<=heigh) ret.push_back({sx,sy}); //起点满足条件 q.push({sx,sy}); auto comp = [&](vector& v1, vector& v2) { int a=grid[v1[0]][v1[1]],b=grid[v2[0]][v2[1]]; return a < b||a==b&&v1<v2; //数组也可以进行比较,于字符串比较原理相同 }; vector<vector> vist(n,vector(m)); //存储已经到达的位置 vist[sx][sy]=1; while(q.size()&&ret.size()<tar) { int _size=q.size(); vector<vector> tmp; //先使用一个临时数组,存放上下所有满足条件坐标 for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k=0&&a=0&&b=low&&grid[a][b]=0&&a=0&&btar) ret.resize(tar); return ret; }};1293. 网格中的最短路径
此题的难点在于，已经扩展过的位置还扩展不扩展了？？？
当第二次扩展到这个位置时，消除的障碍物比上一次少才向这个位置扩展，否则不向这个位置扩展，可以通过一个int vist[n][m]的数组来记录到达该位置时消除障碍物的个数。
具体解法看以下代码：
struct Step{ int _x,_y; //该位置的坐标 int _rest; //到达该位置时剩余可以消除障碍物的个数 Step(int x,int y,int rest):_x(x),_y(y),_rest(rest){}};class Solution {public: int shortestPath(vector<vector>& grid, int k) { //使用BFS,只不过在向外进行扩展的时候,对每个位置记录以下已经移除的障碍物的个数 int n=grid.size(),m=grid[0].size(),step=0; if(n==1&&m==1) return 0; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; k=min(k,m+n-3); //做多会移除m+n-3个障碍物,所以可以对此处进行剪枝 vector<vector> vist(n,vector(m,-1)); //记录到达每个位置剩余移除障碍物的次数 vist[0][0]=k; queue q; q.push(Step(0,0,k)); while(!q.empty()) { int _size=q.size(); for(int i=0;i<_size;i++) { int x=q.front()._x,y=q.front()._y; int rest=q.front()._rest; if(x==n-1&&y==m-1) return step; q.pop(); for(int k=0;k=0&&a=0&&b<m) { if(grid[a][b]) tmp--; //是障碍物 if(tmpvist[a][b]) //没有到达的位置或已经达到了但是剩余次数较少 { q.push(Step(a,b,tmp)); vist[a][b]=tmp; } } } } step++; } return -1; }};909. 蛇梯棋
要求最短路径，毫无疑问考虑BFS，但是此题根据背景介绍：每个格子都有编号，编号的顺序还是蛇形的。那么必定需要将编号转换为坐标。
BFS中的队列存放什么，是存放坐标还是编号？？？
存放编号会更好一些，因为如果存放坐标，每次将坐标拿出来后还是需要转化为编号，再转换为坐标，多了一步转化。而存放编号的话就只需要考虑将编号转化为坐标.
class Solution {public: int snakesAndLadders(vector<vector>& board) { //根据题意需要找最短路径,考虑使用BFS //此题的BFS中的队列存放什么？？？存放左边还是编号？？？ //用队列存储编号 //根据编号pos计算横坐标:从下往上行为r=(pos-1)%n,那么从上往下就是n-1-r //计算纵坐标,如果r为偶数,纵坐标就是l=(pos-1)%n;如果r是奇数,纵坐标就是n-1-l int n=board.size(), step=0; vector vist(n*n+1); //记录那些编号已经去过了 vist[1]=1; queue q; //记录编号 q.push(1); while(!q.empty()) { int _size=q.size(); for(int i=0;i<_size;i++) { int pos=q.front(); q.pop(); if(pos==n*n) return step; for(int k=1;k<=6&&pos+k<=n*n;k++) { int new_pos = pos + k; int _r = (new_pos - 1) / n, r = n - 1 - _r; int _l = (new_pos - 1) % n; if (_r % 2 != 0) _l = n - 1 - _l; //将编号转化为坐标 if(board[r][_l]!=-1) new_pos=board[r][_l]; if(vist[new_pos]) continue; //如果该位置已经来过,就不需要再走了 vist[new_pos]=1; q.push(new_pos); } } step++; } return -1; }};1210. 穿过迷宫的最少移动次数
按照题目要求使用BFS即可，只不过：
蛇头在一个位置又两种方向，分别是向下和向右，所以在检查一个方向是否需要进入的时候就出现了分歧，上一次到达这个位置蛇向右，这一次蛇向下，怎么进行区分呢？？
将二维数组vector<vector> vist变成三维数组vector<vector<vector>> 不仅记录已经走过的位置，还记录走到这个位置时是什么方向即可。
class Solution {public: int minimumMoves(vector<vector>& grid) { //使用BFS,只需要记录蛇身的方向 int n=grid.size(),m=grid[0].size(),step=0; const int RIGHT=1; const int DOWN=2; queue<vector> q; q.push({0,1,RIGHT}); vector<vector<vector>> vist(n,vector<vector>(m,vector(2)));//使用两个变量其中0表示竖直方向,1表示水平方向 vist[0][1][1]=1; while(!q.empty()) { int _size=q.size(); for(int i=0;i<_size;i++) { int x=q.front()[0],y=q.front()[1],dir=q.front()[2]; q.pop(); if(x==n-1&&y==n-1&&dir==RIGHT) return step; if(dir==RIGHT) { //向右 if(y+1<m&&!grid[x][y+1]&&!vist[x][y+1][1]) { q.push({x,y+1,RIGHT}); vist[x][y+1][1]=1; } //旋转 if(x + 1 < n && !grid[x + 1][y] && !grid[x + 1][y-1]&&!vist[x+1][y-1][0]) { q.push({x+1,y-1,DOWN}); vist[x+1][y-1][0]=1; } //整体向下移动 if(x+1<n&&!grid[x+1][y-1]&&!grid[x+1][y]&&!vist[x+1][y][1]) { q.push({x+1,y,RIGHT}); vist[x+1][y][1]=1; } } else { if(x+1<n&&!grid[x+1][y]&&!vist[x+1][y][0]) { q.push({x+1,y,DOWN}); vist[x+1][y][0]=1; } if(y+1<m&&!grid[x][y+1]&&!grid[x-1][y+1]&&!vist[x-1][y+1][1]) { q.push({x-1,y+1,RIGHT}); vist[x-1][y+1][1]=1; } //整体向右 if(y+1<n&&!grid[x-1][y+1]&&!grid[x][y+1]&&!vist[x][y+1][0]) { q.push({x,y+1,DOWN}); vist[x][y+1][0]=1; } } } step++; } return -1; }};675. 为高尔夫比赛砍树
每一次砍掉的树必须是剩余树中最小的，那么总体来说砍树的顺序是固定的，就是从一个位置到最小高度的树的最小距离，只不过需要进行多次而已。
这不就相当于从一个a位置到另一个b位置的最短路径，再从b位置到c位置的最短路径嘛，这样此题就抽象为了多次BFS找最小路径 。
class Solution {public: int cutOffTree(vector<vector>& forest) { //进行模拟 //使用BFS,其中BFS的起点是在改变的 int n=forest.size(),m=forest[0].size(); int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; priority_queue<vector,vector<vector>,greater<vector>> pq; //对树的高度进行排序,带上坐标 for(int i=0;i<n;i++) for(int j=0;j1) pq.push({forest[i][j],i,j}); int xi=0,yi=0,tar_x,tar_y,ret=0; function bfs=[&](int _x,int _y) //进行BFS,从一个位置找最小位置需要的步数 { vector<vector> vist(n,vector(m)); vist[_x][_y]=1; queue<pair> q; q.push({_x,_y}); int step=0; while(!q.empty()) { int _size=q.size(); for(int i=0;i<_size;i++) { int x=q.front().first,y=q.front().second; q.pop(); if(x==tar_x&&y==tar_y) return step; for(int k=0;k=0&&a=0&&b<m&&forest[a][b]&&!vist[a][b]) { vist[a][b]=1; q.push({a,b}); } } } step++; } return -1; }; while(pq.size()) { auto tmp=pq.top(); pq.pop(); tar_x=tmp[1],tar_y=tmp[2]; int step=bfs(xi,yi); //求需要多少步走到最小树的位置 if(step==-1) return -1; else ret+=step; xi=tar_x,yi=tar_y; //记录下一次走的起始位置 } return ret; }};总结
BFS类型得题目在总体而言套路都是差不多得都是使用队列来记录每一次向外进行扩展得结果，只不过每一次都需要判断能否将扩展得位置加入到队列中。
对于一些有难度得BFS题型，经常会出现一个位置多种状态，需要特别注意加入队列得判断条件。还有可能出现BFS的套用，比如最后一个高尔夫比赛砍树，将每一步进行拆分就不难发现，其每一步都是一个BFS。
