C++：用bfs解决洪水覆盖问题与最短路问题习题

1. flood fill(洪水覆盖)算法

岛屿数量

力扣 200(题号)200. 岛屿数量 - 力扣（LeetCode）

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'=

思路

这个题就是寻找岛屿的数量，我们遍历整张地图遇到陆地(并且陆地没被状态数组标记)就进行bfs，利用状态数组将联通的陆地都标记为走过(防止下一次同一块岛屿被bfs继续查找)统计进行了几次bfs即可

ac代码

class Solution {
public:bool states[310][310];void bfs2(vector<vector<char>>& grid, int x,int y)
{ int n=grid.size();int m=grid[0].size();queue<pair<int,int>> qu;qu.push({x,y});int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};states[x][y]=true;//走过while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=n||y2<0||y2>=m)//越界continue;if(grid[x2][y2]=='0')//是海洋continue;if(states[x2][y2])//走过了continue;cout<<x2<<" "<<y2<<endl;states[x2][y2]=true;//标记此处已经走过qu.push({x2,y2});//入队}}// for(int i=0;i<n;i++)// {//     for(int j=0;j<m;j++)//     {//         cout<<states[i][j]<<"  ";//     }//     cout<<endl;// }    }int numIslands(vector<vector<char>>& grid) {int n=grid.size();int m=grid[0].size();cout<<n<<" "<<m<<endl;memset(states,false,sizeof(states));int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='1'&&!states[i][j]){bfs2(grid,i,j);cnt++;}}}return cnt;}
};

被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

思路

遍历整个地图遇见'O'就进入bfs查看这一整个O区域是否靠近边缘并用状态数组1来标记其已经走过，避免重复进入bfs。不靠近边缘的区域我们遍历状态数组将标记走过的变为'X' 但是要注意状态数组1可能将其他靠近边缘的也标记走过了，所以我们要用状态数组2来改变(状态数组2标记这一次bfs所标记的,每次都重置)

ac代码

class Solution {
public:void bfs(vector<vector<char>>& board,int x,int y){int m=board.size();int n=board[0].size();int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};queue<pair<int,int>> qu;qu.push({x,y});states1[x][y]=true;states2[x][y]=true;bool f=true;//查看有没有在地图边缘的while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n){f=false;//在地图边缘cout<<x1<<"  "<<y1<<endl;continue;}if(board[x2][y2]=='X'||states1[x2][y2])//是X或者走过continue;states1[x2][y2]=true;states2[x2][y2]=true;//记录这一次qu.push({x2,y2});}}if(f)//不在地图边缘{for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(states2[i][j])board[i][j]='X';}}}elsememset(states2,false,sizeof(states2));//}void solve(vector<vector<char>>& board) {int m=board.size();int n=board[0].size();memset(states1,false,sizeof(states1));memset(states2,false,sizeof(states2));//for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='O'&&!states1[i][j]){cout<<"开始"<<i<<" "<<j<<endl;bfs(board,i,j);}}}}private:bool states1[210][210];//记录总共走过的bool states2[210][210];//记录这一次走过的
};

岛屿的最大面积

LCR 105. 岛屿的最大面积 - 力扣（LeetCode）

思路

这个题目也很简单，我们同样是遍历整个地图，找到没走过的陆地后进入bfs，将连起来的陆地进行统计，最后与之前记录的最大陆地面积进行比较如果更大就更新最大陆地面积。

ac代码

class Solution {
public:void bfs(vector<vector<int>>& grid,int x,int y){int n=grid.size();int m=grid[0].size();int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};queue<pair<int,int>> qu;qu.push({x,y});states[x][y]=true;int cnt=1;while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=n||y2<0||y2>=m)//越界continue;if(grid[x2][y2]==0||states[x2][y2])//是海或者走过continue;states[x2][y2]=true;qu.push({x2,y2});cnt++;//陆地数量}}cntmax=max(cnt,cntmax);} int maxAreaOfIsland(vector<vector<int>>& grid) {memset(states,false,sizeof(states));int n=grid.size();int m=grid[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&!states[i][j]){// cout<<"mm"<<endl;bfs(grid,i,j);}}}return cntmax;}private:int cntmax=0;bool states[51][51];
};

全球变暖

1233. 全球变暖 - AcWing题库

思路

我们遍历整张地图，遇到没有走过的陆地'#'就进入bfs，由于题目要求查找完全淹没的岛屿数量而陆地临海就会被淹没，所以我们要增加两个变量，分别统计临海的陆地和所有的陆地数量，如果这两者相等就说明这个岛屿会被完全淹没。

ac代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;int n;
char map[1010][1010];
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
queue<pair<int,int>> qu;
bool states[1010][1010];int cnt=0;
void bfs(int x,int y,int &sum1,int &sum2)
{qu.push({x,y});states[x][y]=true;while(!qu.empty()){auto t=qu.front();sum1++;qu.pop();bool falg=false;for(int i=0;i<4;i++){int a=t.first+dx[i];int b=t.second+dy[i];if(a<0||b<0||a>=n||b>=n) continue;if(states[a][b]) continue;//已经走过的if(map[a][b]=='.'){falg=true;//说明上一个邻海continue;}qu.push({a,b});states[a][b]=true;}if(falg) sum2++;//统计临海的数量}if(sum2==sum1)cnt++;}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){ cin>>map[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){ int cnt1=0;//记录岛屿边缘数量int cnt2=0;//记录岛屿陆地数量if(!states[i][j]&&map[i][j]=='#')bfs(i,j,cnt1,cnt2);}   }cout<<cnt<<endl;return 0;
}

2. bfs解决最短路问题

边权都为1时(边权相同时)，从起点开始来一次bfs即可

扩展的层数就是最短路的长度

迷宫中离入口最近的出口

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

提示：

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] 要么是 '.' ，要么是 '+' 。
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance 一定是空格子。

思路

找出口，自己初始位置不能是出口，很简单，我们将初始位置入队，状态数组用来记录走的步数没走过的地方初始化为-1。当走到边界时判断是否是初始位置，不是就返回。

ac代码

class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m=maze.size();int n=maze[0].size();memset(states,-1,sizeof states);int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};queue<pair<int,int>> qu;qu.push({entrance[0],entrance[1]});states[entrance[0]][entrance[1]]=0;while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n){if(x1!=entrance[0]||y1!=entrance[1])//不是开始的坐标{return states[x1][y1];}continue;}if(states[x2][y2]!=-1||maze[x2][y2]=='+')//走过或是墙{continue;}states[x2][y2]=states[x1][y1]+1;qu.push({x2,y2});}}return -1;}private:int states[110][110];
};

最小基因变化

433. 最小基因变化 - 力扣（LeetCode）

提示：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

思路

这个题就是求最开始的字符串转换为最终的字符串，但是所有转换的可能都被记录在基因库数组中了，我们将最开始字符串加入队列，寻找没有变异过(即没有变异成这个基因字符串过)并且与上一个基因只差一个的基因字符串(通过cmp)，一直到最终的字符串返回其次数，没到最终字符串队列空了就返回-1，状态数组用哈希表来实现，将基因库数组全都记录为-1(没变成过),初始序列记录为0。之后每变一次+1。

ac代码

class Solution {
public:bool cmp(string &s1,string& s2){int sum=0;for(int i=0;i<s1.size();i++){if(s1[i]!=s2[i]){sum++;}if(sum>=2)return false;}if(sum==1)return true;elsereturn false;}int bfs(string& startGene,string& endGene,vector<string>& bank){int n=bank.size();//记录个数queue<string> qu;qu.push(startGene);m[startGene]=0;while(!qu.empty()){string tmp=qu.front();qu.pop();for(int i=0;i<n;i++){if(m[bank[i]]!=-1)//查过了continue;if(cmp(tmp,bank[i]))//与这个相差一个{qu.push(bank[i]);m[bank[i]]=m[tmp]+1;if(bank[i]==endGene)return m[endGene];}}}return -1;}int minMutation(string startGene, string endGene, vector<string>& bank) {for(int i=0;i<bank.size();i++){m[bank[i]]=-1;}return bfs(startGene,endGene,bank);}unordered_map<string,int> m;//哈希记录距离
};

单词接龙

LCR 108. 单词接龙 - 力扣（LeetCode）

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

思路

与上题一模一样

ac代码

class Solution {
public:bool cmp(string &s1,string& s2){int sum=0;for(int i=0;i<s1.size();i++){if(s1[i]!=s2[i]){sum++;}if(sum>=2)return false;}if(sum==1)return true;elsereturn false;}int bfs(string& beginWord, string& endWord, vector<string>& wordList){int n=wordList.size();//记录个数queue<string> qu;qu.push(beginWord);m[beginWord]=1;while(!qu.empty()){string tmp=qu.front();qu.pop();for(int i=0;i<n;i++){if(m[wordList[i]]!=-1)//查过了continue;if(cmp(tmp,wordList[i]))//与这个相差一个{qu.push(wordList[i]);m[wordList[i]]=m[tmp]+1;if(wordList[i]==endWord)return m[endWord];}}}return 0;}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {for(int i=0;i<wordList.size();i++){m[wordList[i]]=-1;}return bfs(beginWord,endWord,wordList);}private:unordered_map<string,int> m;
};

为高尔夫比赛砍树

提示：

m == forest.length
n == forest[i].length
1 <= m, n <= 50
0 <= forest[i][j] <= 109

思路

要注意一个点，有树的地方也是可以走的。我们要由低的树砍然后砍次低的树一次递推。如上面实例1 拆分来看就是先求最小的树2的距离再求次小的数3的距离，将这些都累加起来

ac代码

class Solution {
public:int bfs(vector<vector<int>>& forest,pair<int,int> p,int ed){if(forest[p.first][p.second]==ed){forest[p.first][p.second]=1;return 0;}int m=forest.size();int n=forest[0].size();        memset(states,-1,sizeof states);int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};queue<pair<int,int>> qu;qu.push(p);states[p.first][p.second]=0;int cnt=0;while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n)continue;if(forest[x2][y2]==0||states[x2][y2]!=-1)//有障碍,或者走过continue;qu.push({x2,y2});states[x2][y2]=states[x1][y1]+1;// cout<<x2<<"  "<<y2<<endl;// cout<<" x2 y2 :"<<states[x2][y2]<<endl;if(forest[x2][y2]==ed){// cout<<x1<<"  "<<y1<<endl;cout<<states[x2][y2]<<"  步数"<<endl;// cout<<"end: "<<ed<<endl;forest[x2][y2]=1;return states[x2][y2];}}}return -1;}int cutOffTree(vector<vector<int>>& forest) {       int m=forest.size();int n=forest[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(forest[i][j]>=2)pq.push_back({forest[i][j],{i,j}});}// cout<<endl;}sort(pq.begin(),pq.end());for(int i=0;i<pq.size();i++){cout<<pq[i].first<<"  ";}int cnt=1;int s=bfs(forest,{0,0},pq[0].first);//找第一个cout<<endl;while(cnt<pq.size()){int tmp=bfs(forest,pq[cnt-1].second,pq[cnt].first);//上一个的起点坐标，cout<<"s="<<s<<endl;if(tmp==-1)return -1;s+=tmp;cnt++;}return s;}private:vector<pair<int,pair<int,int>>> pq;int states[51][51];
};

这篇就到这里啦(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤