[USACO08FEB] Meteor Shower S BFS-Toy模板网

这篇具有很好参考价值的文章主要介绍了[USACO08FEB] Meteor Shower S BFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

共有 $M$ 颗流星 $(1 \leq M \leq 50000)$ 会坠落在农场上，其中第 $i$ 颗流星会在时刻 $T_i$ 砸在坐标为 $X_i,Y_i)(0≤X_i,Y_i≤300)$ 的格子里。流星会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，无法在这些格子上行走。贝茜在时刻 $0$ 开始行动，只能在第一象限中，平行于坐标轴行动，每 $1$ 个时刻中，移动到相邻的格子中。计算最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $- 1$ 。
本题要求计算最少需要多少时间可以看出需要使用广度搜索，需要注意的是我们需要计算每个格子化为焦土的时间，这个时间应该是最小值。文章来源地址https://www.toymoban.com/news/detail-613525.html

#include<bits/stdc++.h>
using namespace std;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int flag[310][310],vis[310][310];
int m,xx,yy,Time;
int ans[301][301];
queue<int> q[2];
int main()
{
	cin>>m;
	memset(flag,-1,sizeof(flag));
	for(int i=1;i<=m;i++)
	{
		cin>>xx>>yy>>Time;
		for(int j=0;j<=4;j++)
		if((xx+dx[j])>=0&&(yy+dy[j])>=0)
		{
			if(flag[xx+dx[j]][yy+dy[j]]!=-1)
			flag[xx+dx[j]][yy+dy[j]]=min(Time,flag[xx+dx[j]][yy+dy[j]]);
			else flag[xx+dx[j]][yy+dy[j]]=Time;
		}
	}
	q[0].push(0);q[1].push(0);
	while(q[0].empty()==0&&q[1].empty()==0)
	{
		int x,y;
		x=q[0].front();y=q[1].front();
		q[0].pop();q[1].pop();
		
		if(flag[x][y]==-1){cout<<ans[x][y]<<endl;return 0;}
		for(int i=1;i<=4;i++)
		{
			int x1=x+dx[i],y1=y+dy[i];
			if(x1>=0&&y1>=0&&vis[x1][y1]!=1&&((flag[x1][y1]>(ans[x][y]+1))||flag[x1][y1]==-1))
			{
			    //cout<<x1<<" "<<y1<<endl;
				q[0].push(x1);q[1].push(y1);
				ans[x1][y1]=ans[x][y]+1;
				vis[x1][y1]=1;
			}
		}
	}
	cout<<"-1"<<endl;
	return 0;
}