编辑距离(多源BFS)

题目描述

给定一个 N 行 M 列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为： dist(A[i][j],A[k][l])=|i−k|+|j−l| 输出一个 N 行 M 列的整数矩阵 B，其中： B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])

输入格式
第一行两个整数 N,M。
接下来一个 N 行 M 列的 01 矩阵，数字之间没有空格。

输出格式
一个 N 行 M 列的矩阵 B，相邻两个整数之间用一个空格隔开。

数据范围
1≤N,M≤1000
输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1

本题是一个多源BFS，求所有点到点为1的距离并输出距离矩阵。
我们可以把所有为1的点当做起点，然后建立一个虚拟源点，虚拟源点到起点的距离为0。

这样做的话我们搜点的时候被搜过的点的距离会不会被再次更新呢？
答案是不会的。因为单源BFS具有两段性

因为我们是一层一层来搜的，每次搜的点必然是比自己大1层的点，根据两段性我们可以推出来它是单调的。
既然它是单调的，那我们前面的点肯定比后面加入的点要小，所以前面被搜过的点就不会被再次更新了。
这样我们就可以把该题转化为单源BFS，该题在做单源BFS的时候不用建立一个真实的虚拟源点，因为虚拟源点到起点（值为1的点）的距离为0，所以我们在做的时候直接把所有起点加入队列中就可以了。

#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'){
      //找到源点
                d[i][j]=0;
                q.push({
    i,j});
            }
        }
        
    }
    while(q.size()){
    
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
      //搜索
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<0 || a>=n || b<0 || b>=m) continue;  //是否越界
            if(d[a][b]!=-1) continue;  //是否走过
            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();
    //输出距离矩阵
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            printf("%d ",d[i][j]);
        }
        puts("");
    }
    
    return 0;
    
}