SSLOJ 1316.血色先锋军

...


题目:

传送门


题意:

给出一张nmn*mn∗m的图以及一些传染源,求各个领主最短被感染到的时间


分析:

在图上,有是普通的一个个向四周传染,所以用典型的bfsbfsbfs解决


代码:

#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;
}
上一篇:【广搜】SSL_1316 血色先锋军


下一篇:[LeetCode] 1593. Split a String Into the Max Number of Unique Substrings