Edit distance (multi-source BFS)

Title Description

Given a N That's ok M Column 01 matrix A,A[i][j] And A[k][l] The Manhattan distance between is defined as ： dist(A[i][j],A[k][l])=|i−k|+|j−l| Output one N That's ok M The integer matrix of columns B, among ： B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])

Input format
The first line has two integers N,M.
Next one N That's ok M Column 01 matrix , There is no space between the numbers .

Output format
One N That's ok M Columns of the matrix B, Two adjacent integers are separated by a space .

Data range
1≤N,M≤1000
sample input ：
3 4
0001
0011
0110
sample output ：
3 2 1 0
2 1 0 0
1 0 0 1

This topic is a multi-source BFS, Find all points to points as 1 And output the distance matrix .
We can divide everything into 1 Point of as the starting point , Then create a virtual source , The distance from the virtual source point to the starting point is 0.

If we do this, will the distance of the searched points be updated again when we search the points ？
The answer is no . Because single source BFS It has two phases

Because we search layer by layer , The point of each search must be bigger than yourself 1 The point of the layer , According to the two-phase property, we can deduce that it is monotonous .
Since it is monotonous , Then the points in front of us must be smaller than those added later , Therefore, the previously searched points will not be updated again .
In this way, we can turn the problem into a single source BFS, This question is doing single source BFS There is no need to create a real virtual source , Because the virtual source point to the starting point （ The value is 1 The point of ） The distance to 0, So when we do it, we can directly add all the starting points to the queue .

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> PII;
const int N=1005;

char g[N][N];
int d[N][N];
queue<PII> q;
int n,m;

void bfs(){
    
    memset(d,-1,sizeof d);
    int dx[]={
    0,1,0,-1},dy[]={
    1,0,-1,0};
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            if(g[i][j]=='1'){
      // Find source point 
                d[i][j]=0;
                q.push({
    i,j});
            }
        }
        
    }
    while(q.size()){
    
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
      // Search for 
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<0 || a>=n || b<0 || b>=m) continue;  // Is it across the border? 
            if(d[a][b]!=-1) continue;  // Have you walked 
            q.push({
    a,b});
            d[a][b]=d[t.first][t.second]+1;
        }
    }
}

int main(){
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            cin>>g[i][j];
        }
    }
    
    bfs();
    // Output distance matrix 
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            printf("%d ",d[i][j]);
        }
        puts("");
    }
    
    return 0;
    
}