黑暗终将笼罩一切
2025-02-06 19:33:36
发布于：上海
29阅读
0回复
0点赞
// 多源BFS
#include<bits/stdc++.h>
using namespace std;
char g[1010][1010];
int dist[1010][1010];
struct node{
int x,y;
int d;
};
int dir[4][2] = {-1,0,1,0,0,1,0,-1};
int n,m;
int main(){
cin>>n>>m;
// #
queue<node> q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='#'){
dist[i][j] = 0;
q.push({i,j,0});
}else dist[i][j] = 1e9;
}
}
int mx = 0;
while(q.size()){
node t = q.front();
q.pop();
mx = max(mx,dist[t.x][t.y]);
for(int i=0;i<4;i++){
int nx = dir[i][0]+t.x;
int ny = dir[i][1]+t.y;
if(nx<1 || ny<1 || nx>n || ny>m)continue;
if(dist[nx][ny]>dist[t.x][t.y]+1){
dist[nx][ny]=dist[t.x][t.y]+1;
q.push({nx,ny});
}
}
}
cout<<mx;
return 0;
}
pipipi 无向图找环 2 拓扑找环+多源BFS
#include<bits/stdc++.h>
using namespace std;
//用拓扑排序求出所有顶点 ，多源BFS
vector<int> tr[3010];
bool vis[3010];
int in[3010];
int dist[3010];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
tr[b].push_back(a);
in[a]++;
in[b]++;
}
queue<int> q;
for(int i=1;i<=n;i++)if(in[i]==1)q.push(i);
while(q.size()){
int u = q.front();
q.pop();
vis[u]=true;
dist[u] = 0x3f3f3f3f;
for(int son:tr[u]){
if(--in[son]==1)q.push(son);
}
}
queue<int> p;
for(int i=1;i<=n;i++)if(!vis[i])p.push(i);
while(p.size()){
int u = p.front();
p.pop();
for(int son:tr[u]){
if(dist[son]>dist[u]+1){
dist[son]=dist[u]+1;
p.push(son);
}
}
}
for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
return 0;
}
这里空空如也
有帮助，赞一个