编辑距离(多源BFS)

编辑距离(多源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 
#include 
#include 
using namespace std;

typedef pair PII;
const int N=1005;

char g[N][N];
int d[N][N];
queue 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 || 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>g[i][j];
        }
    }
    
    bfs();
    //输出距离矩阵
    for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5698297.html