Multi source BFS problem template (with questions)

Title Description ： There are multiple starting points , Find the shortest path from all points to different starting points .

practice ： Add all starting points to the queue and use bfs To do it .

Simple proof ：

You can add a virtual starting point before all the starting points , The path length from this virtual starting point to all starting points is 0.

  Then find the shortest distance from all points to the starting point , Is to find the shortest distance from all points to this virtual starting point .

Since the weight from the virtual starting point to all edges is 0, So you can add all the starting points to the queue .

1162. As Far from Land as Possible

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|

The question ： Please all 0 Medium to all 1 The maximum value of the shortest distance .

hold 1 Add to the queue as a starting point , And then use bfs To do it . 

#define x first
#define y second
typedef pair<int,int> PII;
class Solution {
public:
    int maxDistance(vector<vector<int>>& g) {
       int n=g.size(),m=g[0].size(),INF=1e8;
       vector<vector<int>>dist(n,vector<int>(m,INF));
       queue<PII>q;
       for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){
               if(g[i][j]){
                   dist[i][j]=0;
                   q.push({i,j});
               }
           }
       }
       int dx[4]={-1,0,1,0};
       int dy[4]={0,1,0,-1};

       while(q.size()){
           auto t =q.front();
           q.pop();
           for(int i=0;i<4;i++){
               int x=t.x+dx[i],y=t.y+dy[i];
               if(x>=0&&y>=0&&x<n&&y<m&&dist[x][y]==INF){
                   dist[x][y]=dist[t.x][t.y]+1;
                   q.push({x,y});
               }
           }
       }
           int res=-1;
           for(int i=0;i<n;i++){
               for(int j=0;j<m;j++){
                   if(!g[i][j]){
                       res=max(res,dist[i][j]);
                   }
               }
           }
           if(res==INF)res=-1;
       
           return res;
    }
    
};