当前位置:网站首页>编辑距离(多源BFS)
编辑距离(多源BFS)
2022-07-06 09:18:00 【小陈同学_】
题目描述
给定一个 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;
}
边栏推荐
- Introduction to the daily practice column of the Blue Bridge Cup
- Database course design: college educational administration management system (including code)
- 抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
- Excel导入,导出功能实现
- 地球围绕太阳转
- Meanings and differences of PV, UV, IP, VV, CV
- Get the position of the nth occurrence of the string
- [offer18] delete the node of the linked list
- [算法] 剑指offer2 golang 面试题12:左右两边子数组的和相等
- 【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
猜你喜欢
Vulnhub target: hacknos_ PLAYER V1.1
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
idea问题记录
Easy to use shortcut keys in idea
Single chip Bluetooth wireless burning
MySQL shutdown is slow
Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
【无标题】
Force buckle 1189 Maximum number of "balloons"
單片機藍牙無線燒錄
随机推荐
Get the position of the nth occurrence of the string
Derivation of logistic regression theory
[offer9] implement queues with two stacks
Expected value (EV)
使用rtknavi进行RT-PPP测试
[Leetcode15]三数之和
MySQL replacement field part content
编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
FairyGUI增益BUFF數值改變的顯示
Fairygui gain buff value change display
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
Programming homework: educational administration management system (C language)
[算法] 剑指offer2 golang 面试题9:乘积小于k的子数组
How to improve the deletion speed of sequential class containers?
FairyGUI增益BUFF数值改变的显示
Particle system for introduction to unity3d Foundation (attribute introduction + case production of flame particle system)
基于rtklib源码进行片上移植的思路分享
Lean product development - Lean Software Development & lean product development
[算法] 剑指offer2 golang 面试题1:整数除法
微信小程序开发心得