Meteor Shower——很坑的基础bfs

作为一名新手菜鸡，我是真的觉得这道bfs坑，写个题解帮助入坑了的小伙伴

题意

：就是这个人在原点处，然后有流星会不定时的撞击到某个点上，上下左右中五个地方都会被破坏。问它能否逃跑，能的话用时多少，不能的话输出-1

思路：模板bfs，注意地图的范围不是在300以内，其余思路见代码注释，本人是新手，代码思路参考了大佬的，但是自己写的，有错误请指正

在这里插入代码片
``#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 305;
int meteor[N+1][N+1] = {
   0};//标记流星撞击的点 
int dx[4] ={
   0,1,0,-1};//左下右上四个方向 
int dy[4] = {
   -1,0,1,0};
int visit[N+1][N+1]={
   0}; 
struct Step
{
   
	int x;
	int y;
	int steps;//代表步数 
};
queue<Step> q;
int main()
{
   
	int m;
	cin>>m;
	int x,y,t;
	memset(meteor,-1,sizeof(meteor));//把所有的点初始化为-1 
	memset(visit,0,sizeof(visit));//判断是否走过 
	while(m--)
	{
   
		cin>>x>>y>>t;
		//这里也很重要 
		if(meteor[x][y]==-1) 	meteor[x][y] = t;
		else 
		{
   
			meteor[x][y] = min(meteor[x][y],t);//有可能同一个点会被撞击多次，
												//我们取最先撞击的那个流星的时间 
		}
		for(int i=0;i<4;i++)
		{
   
			int nextx = x+dx[i];
			int nexty = y+dy[i];
			if(nextx<0||nexty<0) continue;
			if(meteor[nextx][nexty]==-1) 	meteor[nextx][nexty] = t;//首先要看这个点的四周的点被撞击过没 
			else 
			{
   
				meteor[nextx][nexty] = min(meteor[nextx][nexty],t);//如果被撞击过，同理取最先的 
			}
		}
	}
	Step begin;
	begin.x = 0;
	begin.y = 0;
	begin.steps =0;
	visit[0][0] = 1;
	q.push(begin);//初始状态：在点（0，0）移动次数为0 

	while(!q.empty())
	{
   
		Step s = q.front();
		q.pop();	
		if(meteor[s.x][s.y]==-1)
		{
   
			cout<<s.steps<<endl;
			return 0;
		}
		for(int i=0;i<4;i++) 
		{
   
				 Step next;
				 next.x = s.x+dx[i];
				 next.y = s.y+dy[i];
				next.steps = s.steps+1;
				if(next.x<0||next.y<0||visit[next.x][next.y]==1) continue;//越界或者走过 ，
				//这里一定不要判断不能大于300，具体上限本人也不是很清楚，但这样可以过，应该没卡数据 
				if(meteor[next.x][next.y]==-1) //安全 就直接结束bfs，这样的结果肯定是最优的 
				{
   
					cout<<next.steps<<endl;
					return 0;
				}
				if(meteor[next.x][next.y]>next.steps)//在到达安全点前，经过的点，
														//被撞击的时间必须大于它到达的时间 
				{
   
					q.push(next);
					visit[next.x][next.y] = 1;
				} 
		} 	
	}
	cout<<"-1"<<endl;//如果不能到达则输出-1，如果在0，0处就被撞死了也是这里输出-1 
	return 0;
}