BFS：多源BFS问题

一、多源BFS简介

 超级源点：其实就是把相应的原点一次性都丢到队列中

二、01矩阵

. - 力扣（LeetCode）

class Solution {
public:const int dx[4]={1,-1,0,0};const int dy[4]={0,0,1,-1};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {//多源BFS  正难则反，以0为起点向外扩展int m=mat.size(),n=mat[0].size();vector<vector<int>> dis(m,vector<int>(n,-1));//要输出的数组 -1表示没有搜索过queue<pair<int,int>> q;//存储起点for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(mat[i][j]==0){q.emplace(i,j);dis[i][j]=0;}//不需要标记数组 不需要step 也不需要控制一层一层出sz//因为dis数组不仅可以标记哪些地方没有搜索过或者搜索过，而且存储了最短距离while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=0&&x<m&&y>=0&&y<n&&dis[x][y]==-1) {dis[x][y]=dis[a][b]+1;q.emplace(x,y);}}}return dis;}
};

三、飞地的数量

. - 力扣（LeetCode）

class Solution {
public:
//正难则反const int dx[4]={1,-1,0,0};const int dy[4]={0,0,1,-1};int numEnclaves(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();//从边开始进行一次宽搜 将可以走出边界的标记一下vector<vector<bool>> vis(m,vector<bool>(n));//将边界1的都丢到队列中queue<pair<int,int>> q;for(int i=0;i<m;++i)//第一行和最后一行for(int j=0;j<n;++j)if(i==0||i==m-1||j==0||j==n-1)if(grid[i][j]==1){q.emplace(i,j);vis[i][j]=true;}//进行多源BFSwhile(!q.empty()){auto [a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&vis[x][y]==false){q.emplace(x,y);vis[x][y]=true;}}}//处理完之后，遍历一下找到没有被标记且为1的单元格 就可以统计个数了int ret=0;for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(grid[i][j]==1&&vis[i][j]==false) ++ret;return ret;}
};

四、地球中的最高点

. - 力扣（LeetCode）

class Solution {
public:const int dx[4]={1,-1,0,0};const int dy[4]={0,0,1,-1};vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int m=isWater.size(),n=isWater[0].size();vector<vector<int>> vv(m,vector<int>(n,-1));//正难则反queue<pair<int,int>> q;for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(isWater[i][j]==1){q.emplace(i,j);vv[i][j]=0;}//多源BFSwhile(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){vv[x][y]=vv[a][b]+1;q.emplace(x,y);}}}return vv;}
};

 五、地图分析

. - 力扣（LeetCode）

class Solution {
public:const int dx[4]={1,-1,0,0};const int dy[4]={0,0,1,-1};int maxDistance(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();vector<vector<int>> vv(m,vector<int>(n,-1));queue<pair<int,int>> q;for(int i=0;i<m;++i) for(int j=0;j<n;++j)if(grid[i][j]==1){q.emplace(i,j);vv[i][j]=0;}//多源BFSint ret=-1;//如果只有海洋或者只有陆地，那么就会直接返回-1while(!q.empty()){auto[a,b]=q.front();q.pop();for(int k=0;k<4;++k){int x=dx[k]+a,y=dy[k]+b;if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){vv[x][y]=vv[a][b]+1;q.emplace(x,y);ret=max(ret,vv[x][y]);}}}return ret;}
};