...
题目:
题意:
给出一张n∗m的图以及一些传染源,求各个领主最短被感染到的时间
分析:
在图上,有是普通的一个个向四周传染,所以用典型的bfs解决
代码:
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define LL long long
inline LL read() {
LL d=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
using namespace std;
queue<pair<LL,LL> > q;
LL t[505][505];
LL n=read(),m=read(),a=read(),b=read();
void bfs()
{
while(q.size())
{
LL u=q.front().first,v=q.front().second;
q.pop();
if(t[u+1][v]>t[u][v]+1&&u+1<=n) t[u+1][v]=t[u][v]+1,q.push(make_pair(u+1,v));
if(t[u-1][v]>t[u][v]+1&&u-1>0) t[u-1][v]=t[u][v]+1,q.push(make_pair(u-1,v));
if(t[u][v+1]>t[u][v]+1&&v+1<=m) t[u][v+1]=t[u][v]+1,q.push(make_pair(u,v+1));
if(t[u][v-1]>t[u][v]+1&&v-1>0) t[u][v-1]=t[u][v]+1,q.push(make_pair(u,v-1));
}
return;
}
int main()
{
memset(t,0x7f7f7f7f,sizeof(t));
LL a1,a2;
for(LL i=1;i<=a;i++)
{
a1=read();a2=read();
t[a1][a2]=0;
q.push(make_pair(a1,a2));
}
bfs();
for(LL i=1;i<=b;i++) {a1=read();a2=read();printf("%d\n",t[a1][a2]);}
return 0;
}