当前位置:网站首页>编辑距离(多源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;
}
边栏推荐
- [Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
- 1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
- Force buckle 1189 Maximum number of "balloons"
- ORA-02030: can only select from fixed tables/views
- Esp8266 connect onenet (old mqtt mode)
- Fabrication of fairygui simple Backpack
- Devops' future: six trends in 2022 and beyond
- Easy to use shortcut keys in idea
- FairyGUI循環列錶
- Mysql database index
猜你喜欢
随机推荐
FairyGUI增益BUFF數值改變的顯示
[offer9]用两个栈实现队列
基本Dos命令
NovAtel 板卡OEM617D配置步骤记录
Special palindromes of daily practice of Blue Bridge Cup
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
FairyGUI简单背包的制作
C programming exercise
SSD technical features
Comparative analysis of the execution efficiency of MySQL 5.7 statistical table records
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
[leetcode622] design circular queue
JUC forkjoin and completable future
Particle system for introduction to unity3d Foundation (attribute introduction + case production of flame particle system)
Database table splitting strategy
Fairygui joystick
Talking about the startup of Oracle Database
FairyGUI人物状态弹窗
idea中导包方法