当前位置:网站首页>Edit distance (multi-source BFS)
Edit distance (multi-source BFS)
2022-07-06 12:56:00 【Classmate Chen_】
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;
}
边栏推荐
- 【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
- [algorithm] sword finger offer2 golang interview question 8: the shortest subarray with a sum greater than or equal to K
- [算法] 剑指offer2 golang 面试题7:数组中和为0的3个数字
- FairyGUI簡單背包的制作
- [leetcode622] design circular queue
- Basic DOS commands
- What are the functions and features of helm or terrain
- Database table splitting strategy
- Meanings and differences of PV, UV, IP, VV, CV
- [Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
猜你喜欢
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
FairyGUI循环列表
FairyGUI按钮动效的混用
Unity3D,阿里云服务器,平台配置
[algorithme] swordfinger offer2 golang question d'entrevue 2: addition binaire
SVN更新后不出现红色感叹号
微信小程序开发心得
NovAtel 板卡OEM617D配置步骤记录
Office prompts that your license is not genuine pop-up box solution
[algorithm] sword finger offer2 golang interview question 6: sum of two numbers in the sorting array
随机推荐
使用rtknavi进行RT-PPP测试
C programming exercise
There is no red exclamation mark after SVN update
idea中导包方法
Idea problem record
Combination of fairygui check box and progress bar
Compile GDAL source code with nmake (win10, vs2022)
It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
Meanings and differences of PV, UV, IP, VV, CV
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
[算法] 剑指offer2 golang 面试题6:排序数组中的两个数字之和
What are the advantages of using SQL in Excel VBA
FairyGUI复选框与进度条的组合使用
2022国赛Re1 baby_tree
Fairygui gain buff value change display
wsl常用命令
[algorithm] sword finger offer2 golang interview question 3: the number of 1 in the binary form of the first n numbers
基于rtklib源码进行片上移植的思路分享
KF UD分解之伪代码实现进阶篇【2】
染色法判定二分图