一、多源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;}
};