分类信息网站排行_网页设计作品展示图片_b站推广2024mmm已更新_电脑版百度网盘

---

前言

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：优选算法
🔑本章内容：BFS解决FloodFill算法+BF解决解决最短路问题
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

---

一、BFS解决FloodFill算法示例：

1.1 图像渲染

1. 题⽬链接：733. 图像渲染

2. 题⽬描述：
   

3. 算法思路：
   可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。

4. C++代码

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int prev=image[sr][sc];if(prev==color)return image;int n=image.size(),m=image[0].size();queue<PII> q;image[sr][sc]=color;q.push({sr,sc});while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&image[x][y]==prev){image[x][y]=color;q.push({x,y});}}}return image;}
};

1.2 岛屿数量

1. 题⽬链接：200. 岛屿数量
2. 题⽬描述：
   
3. 算法思路：
   遍历整个矩阵，每次找到「⼀块陆地」的时候：
   • 说明找到「⼀个岛屿」，记录到最终结果 ret ⾥⾯；
   • 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。
   • 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是 733. 图像渲染 这道题~
   这样，当我们，遍历完全部的矩阵的时候， ret 存的就是最终结果。
4. C++代码

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int n,m;int cnt=0;
public:void bfs(int i,int j,vector<vector<char>>& grid){queue<PII> q;q.push({i,j});while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]=='1'){q.push({x,y});grid[x][y]='0';}}}}int numIslands(vector<vector<char>>& grid) {n=grid.size();m=grid[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='1'){grid[i][j]='0';bfs(i,j,grid);cnt++;}}}return cnt;}
};

1.3 岛屿的最⼤⾯积

1. 题⽬链接：695. 岛屿的最⼤⾯积
2. 题⽬描述：
   
3. 算法思路：
   • 遍历整个矩阵，每当遇到⼀块⼟地的时候，就⽤「深搜」或者「宽搜」将与这块⼟地相连的「整个岛屿」的⾯积计算出来。
   • 然后在搜索得到的「所有的岛屿⾯积」求⼀个「最⼤值」即可。
   • 在搜索过程中，为了「防⽌搜到重复的⼟地」：
   ◦ 可以开⼀个同等规模的「布尔数组」，标记⼀下这个位置是否已经被访问过；
   ◦ 也可以将原始矩阵的 1 修改成 0 ，但是这样操作会修改原始矩阵。
4. C++代码

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int n,m;int ret=0,maxsum=0;int flag[55][55]={0};//标记访问过的点
public:int bfs(int i,int j,vector<vector<int>>& grid){queue<PII> q;q.push({i,j});int ret=0;while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1&&flag[x][y]==0){q.push({x,y});//grid[x][y]=0;flag[x][y]=1;}}ret++;}return ret;}int maxAreaOfIsland(vector<vector<int>>& grid) {n=grid.size();m=grid[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&flag[i][j]==0){//grid[i][j]=0;flag[i][j]=1;int cnt=bfs(i,j,grid);maxsum=max(maxsum,cnt);}}}return maxsum;}
};

1.4 被围绕的区域

1. 题⽬链接：130. 被围绕的区域
2. 题⽬描述：
   
3. 解法：
   算法思路：正难则反。
   可以先利⽤ bfs 将与边缘相连的 ‘0’ 区域做上标记，然后重新遍历矩阵，将没有标记过的 ‘0’ 修改成 ‘X’ 即可。
4. C++代码

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int n,m;int flag[210][210]={0};
public:void bfs(int i,int j,vector<vector<char>>& board){queue<PII> q;q.push({i,j});while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&board[x][y]=='O'&&flag[x][y]==0){q.push({x,y});flag[x][y]=1;}}}}void solve(vector<vector<char>>& board) {n=board.size();m=board[0].size();for(int j=0;j<m;j++){if(board[0][j]=='O'&&flag[0][j]==0){flag[0][j]=1;bfs(0,j,board);}if(board[n-1][j]=='O'&&flag[n-1][j]==0){flag[n-1][j]=1;bfs(n-1,j,board);}}for(int i=0;i<n;i++){if(board[i][0]=='O'&&flag[i][0]==0){flag[i][0]=1;bfs(i,0,board);}if(board[i][m-1]=='O'&&flag[i][m-1]==0){flag[i][m-1]=1;bfs(i,m-1,board);}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='O'&&flag[i][j]==0)board[i][j]='X';}}}
};

二、BFS解决最短路问题

2.1 迷宫中离⼊⼝最近的出⼝

1. 题⽬链接：1926. 迷宫中离⼊⼝最近的出⼝

2. 题⽬描述：
   

3. 解法（bfs 求最短路）：
   算法思路：
   利⽤层序遍历来解决迷宫问题，是最经典的做法。
   我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离。

4. C++代码

class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int flag[110][110]={0};typedef pair<int,int> PII;int cnt=0;
public:int bfs(int i,int j,vector<vector<char>>& maze){queue<PII> q;q.push({i,j});while(!q.empty()){cnt++;int sz=q.size();while(sz--){auto[a,b]=q.front();//这里为什么不可以用&q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&maze[x][y]=='.'&&flag[x][y]==0){if(x==0||x==n-1||y==0||y==m-1)return cnt;q.push({x,y});flag[x][y]=1;}}}}return -1;}int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {n=maze.size();m=maze[0].size();int a=entrance[0],b=entrance[1];flag[a][b]=1;return bfs(a,b,maze);}
};

2.2 最⼩基因变化

1. 题⽬链接：433. 最⼩基因变化
2. 题⽬描述：
   
3. 解法：
   算法思路：
   如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1 的最短路问题」。因此，从起始的字符串开始，来⼀次 bfs 即可。
4. C++代码

class Solution {int ans=0;char change[4]={'A','C','G','T'};
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> hash(bank.begin(),bank.end());unordered_set<string> vis;if(!hash.count(endGene))return -1;queue<string> q;q.push(startGene);vis.insert(startGene);while(!q.empty()){ans++;int sz=q.size();while(sz--){string s=q.front();q.pop();for(int i=0;i<s.size();i++){string tmp=s;for(int ch=0;ch<4;ch++){tmp[i]=change[ch];if(hash.count(tmp)&&!vis.count(tmp)){if(tmp==endGene)return ans;q.push(tmp);vis.insert(tmp);}}}}}return -1;}
};

2.3 单词接⻰

1. 题⽬链接：127. 单词接⻰
2. 题⽬描述：
   
3. 解法：和上题一样
4. C++代码

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> hash(wordList.begin(),wordList.end());unordered_set<string> vis;if(!hash.count(endWord))return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int cns=1;while(q.size()){cns++;int sz=q.size();while(sz--){string tmp=q.front();q.pop();for(int i=0;i<tmp.size();i++){string t=tmp;//换个临时变量是为防止tmp被改变for(int j='a';j<='z';j++){t[i]=j;if(hash.count(t)&&!vis.count(t)){if(t==endWord)return cns;q.push(t);vis.insert(t);}}}}}return 0;}
};

2.4 为⾼尔夫⽐赛砍树

1. 题⽬链接：675. 为⾼尔夫⽐赛砍树
2. 题⽬描述：
   
3. 解法：
   算法思路：
   a. 先找出砍树的顺序；
   b. 然后按照砍树的顺序，⼀个⼀个的⽤ bfs 求出最短路即可。
4. C++代码

class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int ans=0;int vis[55][55]={0};
public:int bfs(int bx,int by,int ex,int ey,vector<vector<int>>& forest){if(bx==ex&&by==ey)return 0;queue<pair<int,int>> q;q.push({bx,by});vis[bx][by]=1;memset(vis,0,sizeof(vis));//这里一定要清空之前的数据int cnt=0;while(!q.empty()){cnt++;int sz=q.size();while(sz--){auto[a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&forest[x][y]&&!vis[x][y]){if(x==ex&&y==ey)return cnt;q.push({x,y});vis[x][y]=1;}}}}return -1;}int cutOffTree(vector<vector<int>>& forest) {n=forest.size();m=forest[0].size();//先找到要砍的树的顺序vector<pair<int,int>> v;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(forest[i][j]>1)v.push_back({i,j});}}sort(v.begin(),v.end(),[&](const pair<int,int>&t1,const pair<int,int>&t2){return forest[t1.first][t1.second]<forest[t2.first][t2.second];});int bx=0,by=0;for(auto&[a,b]:v){int ret=bfs(bx,by,a,b,forest);if(ret==-1)return -1;ans+=ret;bx=a;by=b;}return ans;}
};