BFS-专题
目录
1.FloodFill
1.1图像渲染
2.岛屿数量
3.岛屿的最大数量
4.被围绕的区域
2.最短路
2.1迷宫中离入口最近的出口
2最小基因变化
3.单词接龙1
4.为高尔夫比赛砍树
3.多源最短路
1. 矩阵
2.飞地的数量
3.地图中的最高点
4.地图分析
1.FloodFill
1.1图像渲染
733. 图像渲染 - 力扣（LeetCode）
本题思路很清晰，就是从当前位置开始，向四周遍历.
唯一要注意的是，如果初始位置的像素值已经等于color了，就直接返回，不然会死循环
class Solution { public: int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; int m,n; struct kp{ int x,y; }; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n)return false; return true; } vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { m=image.size(),n=image[0].size(); int initcolor=image[sr][sc]; if(initcolor==color)return image; queue<kp>mp; mp.push({sr,sc}); image[sr][sc]=color; while(mp.size()>0) { auto tmp=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=tmp.x+dx[i],ny=tmp.y+dy[i]; if(check(nx,ny)&&image[nx][ny]==initcolor) { image[nx][ny]=color; mp.push({nx,ny}); } } } return image; } };
2.岛屿数量
200. 岛屿数量 - 力扣（LeetCode）
记得把while里面的i看作另一个i，这里写得不严谨
class Solution { public: int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n||(*flag)[x][y])return false; return true; } int numIslands(vector<vector<char>>& grid) { m=grid.size(); n=grid[0].size(); flag=new vector<vector<bool>>(m,vector<bool>(n,false)); queue<pair<int,int>>mp; int ans=0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(grid[i][j]=='1'&&(*flag)[i][j]==false) { mp.push({i,j}); ans++; (*flag)[i][j]=true; while(mp.size()>0) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(check(nx,ny)&&grid[nx][ny]=='1') { (*flag)[nx][ny]=true; mp.push({nx,ny}); } } } } } } return ans; } vector<vector<bool>>*flag; int m,n; };
3.岛屿的最大数量
695. 岛屿的最大面积 - 力扣（LeetCode）
class Solution { public: bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n||(*flag)[x][y])return false; return true; } int maxAreaOfIsland(vector<vector<int>>& grid) { m=grid.size(); n=grid[0].size(); flag=new vector<vector<bool>>(m,vector<bool>(n,false)); int ans=0; queue<pair<int,int>>mp; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(grid[i][j]==1&&(*flag)[i][j]==false) { int res=1; mp.push({i,j}); (*flag)[i][j]=true; while(mp.size()>0) { auto [x,y]=mp.front(); mp.pop(); for(int k=0;k<4;k++) { int nx=x+dx[k],ny=y+dy[k]; if(check(nx,ny)&&grid[nx][ny]==1) { res++; (*flag)[nx][ny]=true; mp.push({nx,ny}); } } } ans=max(ans,res); } } } return ans; } int m,n; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; vector<vector<bool>>*flag; };
4.被围绕的区域
130. 被围绕的区域 - 力扣（LeetCode）
这题不是死找，要先把四周一圈处理下。让边缘的O及其连接的O全部先处理成#号。
然后再遍历整个地图，#号修改成O，O修改成X
class Solution { public: bool check(int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n ) return false; return true; } void bfs(vector<vector<char>>& board, int i, int j) { queue<pair<int, int>> mp; mp.push({i, j}); board[i][j] = '#'; while (mp.size() > 0) { auto [x, y] = mp.front(); mp.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (check(nx, ny) && board[nx][ny] == 'O') { mp.push({nx, ny}); board[nx][ny] = '#'; } } } } void solve(vector<vector<char>>& board) { m = board.size(), n = board[0].size(); for (int i = 0; i < m; i++) { if (board[i][0] == 'O')bfs(board, i, 0); if(board[i][n-1]=='O')bfs(board, i, n-1); } for(int j=0;j<n;j++) { if(board[0][j]=='O')bfs(board, 0, j); if(board[m-1][j]=='O')bfs(board, m-1, j); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == '#') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } int m, n; int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; };
2.最短路
2.1迷宫中离入口最近的出口
1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
思路就是bfs找最短路
class Solution { public: int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; int m,n; vector<vector<bool>>*vis; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n||(*vis)[x][y])return false; return true; } int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { m=maze.size(); n=maze[0].size(); vis=new vector<vector<bool>>(m,vector<bool>(n,false)); int sx=entrance[0],sy=entrance[1]; queue<pair<int,int>>mp; mp.push({sx,sy}); (*vis)[sx][sy]=true; int step=0; while(mp.size()) { step++; int sz=mp.size(); while(sz--) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(check(nx,ny)&&maze[nx][ny]=='.') { if(nx==0||nx==m-1||ny==0||ny==n-1) { return step; } mp.push({nx,ny}); (*vis)[nx][ny]=true; } } } } return -1; } };2最小基因变化
433. 最小基因变化 - 力扣（LeetCode）
class Solution { public: vector<bool>*vis; int m; bool check(string &a,string &b) { int cnt=0; for(int i=0;i<8;i++) { if(a[i]!=b[i])cnt++; if(cnt>1)return false; } return true; } int minMutation(string startGene, string endGene, vector<string>& bank) { if(startGene==endGene)return 0; if(bank.size()==0)return -1; m=bank.size(); vis=new vector<bool>(m,false); queue<string>mp; mp.push(startGene); int step=0; while(mp.size()) { step++; int sz=mp.size(); while(sz--) { auto tmp=mp.front(); mp.pop(); for(int i=0;i<m;i++) { if((*vis)[i]==false&&tmp!=bank[i]&&check(tmp,bank[i])) { (*vis)[i]=true; mp.push(bank[i]); if(bank[i]==endGene) { return step; } } } } } return -1; } };3.单词接龙1
127. 单词接龙 - 力扣（LeetCode）
因为数据量不大，所以我先是写了个暴力BFS，然后是卡着点过的，时间复杂度很高。
version1:
class Solution { public: bool check(string a,string b) { int cnt=0; for(int i=0;i<a.size();i++) { if(a[i]!=b[i])cnt++; if(cnt>=2)return false; } return true; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { if(beginWord==endWord)return 2; if(wordList.size()==0)return 0; int m=wordList.size(); vis=new vector<bool>(m,false); queue<string>mp; mp.push(beginWord); int step=1; while(mp.size()>0) { step++; int sz=mp.size(); while(sz--) { auto tmp=mp.front(); mp.pop(); for(int i=0;i<m;i++) { if((*vis)[i]==false&&tmp!=wordList[i]&&check(tmp,wordList[i])) { if(wordList[i]==endWord)return step; (*vis)[i]=true; mp.push(wordList[i]); } } } } return 0; } vector<bool>*vis; };version2:
主要是修改了判断条件，不再用暴力判断，而是利用map和set，快速判断。
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> hash1(wordList.begin(), wordList.end()); if(hash1.find(endWord)==hash1.end())return 0; queue<string> mp; unordered_map<string,int>vis; mp.push(beginWord); vis[beginWord]=1; int step = 1; while (mp.size() > 0) { int sz = mp.size(); step++; while (sz--) { auto tmp = mp.front(); mp.pop(); int m = tmp.size(); for (int i = 0; i < m; i++) { for (char j = 'a'; j <= 'z'; j++) { if (tmp[i] == j) continue; char t = tmp[i]; tmp[i] = j; if (tmp == endWord) return step; if (hash1.find(tmp)!=hash1.end()&&vis[tmp]==0) { mp.push(tmp); hash1.insert(tmp); vis[tmp]=1; } tmp[i]=t; } } } } return 0; } };4.为高尔夫比赛砍树
675. 为高尔夫比赛砍树 - 力扣（LeetCode）
一开始，我想着一次性完成，然后发现实现不了，于是把整个bfs，分成多个bfs。
class Solution { public: int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; int m,n; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n)return false; return true; } class kp{ public: kp(int _x=0,int _y=0,int _index=0) { x=_x,y=_y,index=_index; } int x=0, y=0, index=-1; }; bool vis[51][51]; int bfs1(int sx,int sy,int c,vector<vector<int>>& forest){ memset(vis,0,sizeof vis); queue<pair<int,int>>mp; mp.push({sx,sy}); vis[sx][sy]=true; int step=0; if(forest[sx][sy]==c)return 0; while(mp.size()>0) { step++; int sz=mp.size(); while(sz--) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(check(nx,ny)&&vis[nx][ny]==false&&forest[nx][ny]!=0) { vis[nx][ny]=true; mp.push({nx,ny}); if(forest[nx][ny]==c) { bx=nx,by=ny; forest[nx][ny]=1; return step; } } } } } return -1; } int cutOffTree(vector<vector<int>>& forest) { m=forest.size();n=forest[0].size(); int ans=0; set<int>value; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(forest[i][j]!=1&&forest[i][j]!=0) { value.insert(forest[i][j]); } } } for (auto &e:value) { int p=bfs1(bx,by,e,forest); if(p==-1)return -1; else ans+=p; } return ans; } int bx=0,by=0; };
3.多源最短路
1. 矩阵
542. 01 矩阵 - 力扣（LeetCode）
version1----写法跟之前的单源差不多，只是把每个起点一起放进去。同时本题要正难则反，所以是把0放进去
class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { queue<pair<int,int>>mp; m=mat.size(),n=mat[0].size(); vector<vector<int>>ret(m,vector<int>(n,0)); vector<vector<bool>>vis(m,vector<bool>(n,false)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(mat[i][j]==0) { mp.push({i,j}); vis[i][j]=true; } } } int step=0; while(mp.size()) { step++; int sz=mp.size(); for(int i=0;i<sz;i++) { auto [x,y]=mp.front(); mp.pop(); for(int j=0;j<4;j++) { int nx=x+dx[j],ny=y+dy[j]; if(check(nx,ny)&&vis[nx][ny]==false) { if(mat[nx][ny]==1)ret[nx][ny]=step; vis[nx][ny]=true; mp.push({nx,ny}); } } } } return ret; } int m,n; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n)return false; return true; } };注意，本题不能直接用静态数组开vis，因为会栈溢出
version2----是没有太多变量，while循坏比较简洁的写法
class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { queue<pair<int,int>>mp; m=mat.size(),n=mat[0].size(); vector<vector<int>>dist(m,vector<int>(n,-1)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(mat[i][j]==0) { mp.push({i,j}); dist[i][j]=0; } } } while(mp.size()) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(check(nx,ny)&&dist[nx][ny]==-1) { dist[nx][ny]=dist[x][y]+1; mp.push({nx,ny}); } } } return dist; } int m,n; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; bool check(int x,int y) { if(x<0||x>=m||y<0||y>=n)return false; return true; } };2.飞地的数量
1020. 飞地的数量 - 力扣（LeetCode）
思路是正难则反，我们可以从边界的1开始遍历bfs，把边界的1都丢进队列中。
然后通过bfs，把跟边界1相连的连通块（值都为1的），全部设置为0。
最后遍历下原始地图，然后统计1的个数即可。
class Solution { public: void bfs(vector<vector<int>>& grid) { queue<pair<int,int>>mp; for(int i=0;i<n;i++) { if(grid[0][i]==1) { mp.push({0,i}); } if(grid[m-1][i]==1) { mp.push({m-1,i}); } } for(int i=0;i<m;i++) { if(grid[i][0]==1) { mp.push({i,0}); } if(grid[i][n-1]==1) { mp.push({i,n-1}); } } while(mp.size()) { auto [x,y]=mp.front(); mp.pop(); grid[x][y]=0; for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1) { mp.push({nx,ny}); grid[nx][ny]=0; } } } } int numEnclaves(vector<vector<int>>& grid) { m=grid.size(); n=grid[0].size(); bfs(grid); int ans=0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(grid[i][j]==1) { ans++; } } } return ans; } int m,n; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; };注意，可以设置vis数组标记有没有搜过，但本题不需要返回原始地图，所以我们直接修改1为0即可。
3.地图中的最高点
1765. 地图中的最高点 - 力扣（LeetCode）
思路就是从把水域全部加到队列。然后bfs找陆地连通块，设置高度为当前+1（贪心思想）
class Solution { public: vector<vector<int>> highestPeak(vector<vector<int>>& isWater) { int m=isWater.size(),n=isWater[0].size(); queue<pair<int,int>>mp; vector<vector<bool>>vis(m,vector<bool>(n,false)); vector<vector<int>>ret(m,vector<int>(n,0)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(isWater[i][j]==1) { mp.push({i,j}); vis[i][j]=true; } } } while(mp.size()) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx>=0&&nx<m&&ny>=0&&ny<n&&vis[nx][ny]==false&&isWater[nx][ny]==0) { ret[nx][ny]=ret[x][y]+1; mp.push({nx,ny}); vis[nx][ny]=true; } } } return ret; } int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; };4.地图分析
1162. 地图分析 - 力扣（LeetCode）
思路就是把陆地丢入队列，然后向外遍历，每次+1，同时更新答案。
class Solution { public: int maxDistance(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); vector<vector<int>>dist(m,vector<int>(n,-1)); queue<pair<int,int>>mp; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(grid[i][j]==1) { mp.push({i,j}); dist[i][j]=0; } } } if(mp.size()==0||mp.size()==m*n)return -1; int ans=0; while(mp.size()) { auto [x,y]=mp.front(); mp.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx>=0&&nx<m&&ny>=0&&ny<n&&dist[nx][ny]==-1) { mp.push({nx,ny}); dist[nx][ny]=dist[x][y]+1; ans=max(ans,dist[nx][ny]); } } } return ans; } int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; };