关于多源BFS,基本上就是单源BFS的简单升级了一下,比如在queue中队头开始时只有一个,我们通过这一个队头去推导其他的东西。而多源最短路就是队头一开始有1-n个可能的数,一个一个去BFS。
题目思路:
这个题就直接把所有的1统计出来放进queue中,每次取出对头进行BFS即可,其中有两个问题:
1.我们BFS如何去找到他是0点,怎么通过0传递到下一个0。
2.如何保证他是最小值,会不会出现值覆盖的现象。
其实第一个问题我们可以直接用dist数组进行标记,一旦有0被靠近的1标记了,那么他自身我们就可以看作是个1,通过这个1我们再去找到下一个0。
第二个问题,不会出现覆盖,因为我们每次赋值之后dist就会变成附近1的dist值加1,dist!=-1(我们初始默认0的dist数组值为-1),我们每次都是取最近的,所以一旦到这个地方,其他的点就无法访问了,一旦访问便是最近距离。
千万别忘了判断数组是否越界,否则会导致段错误文章来源:https://www.toymoban.com/news/detail-611216.html
#include<bits/stdc++.h>
using namespace std;
char g[1010][1010];
int n,m;
int dist[1010][1010];
typedef pair<int,int> PII;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
void bfs()
{
memset(dist,-1,sizeof(dist));
queue<PII> q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='1')
{
q.push({i,j});
dist[i][j]=0;
}
}
}
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x<1||x>n||y<1||y>m)
continue;
if(dist[x][y]!=-1)
{
continue;
}
else
{
dist[x][y]=dist[t.first][t.second]+1;
q.push({x,y});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
bfs();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-611216.html
到了这里,关于多源BFS-- 矩阵距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!