题解 | #[USACO 2008 Feb S]Meteor Shower#

这道题主要的坑就是300以外是安全区不是固定到300以内（反正这个坑我找了半天 一直都是最后一个通过不了）
我的思路：先将place数组全部置为-1，在读入流星数据的时候就将该点和周围的点设置为撞击时间（如果两个流星都要撞击就选择时间短的那个），在找路径的时候将现在的时间与撞击时间比较就行，当找到-1时就表示这就是安全区
最后设置一个visit数组减少多余路径就行了

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node{
    int x,y,t;
    node(int xx,int yy,int tt):x(xx),y(yy),t(tt){}
    node(){}
};
int place[305][305];
int visit[305][305];
int dx[]={1,-1,0,0,0};
int dy[]={0,0,1,-1,0};
queue<node> q;
int main()
{
    int M,x,y,t;
    cin>>M;
    memset(place,-1,sizeof(place));
    for(int i=0;i<M;i++){//读入流星数据 并设置爆炸时间
        cin>>x>>y>>t;
        for(int j=0;j<5;j++){
            int tox=x+dx[j];
            int toy=y+dy[j];
            if(tox<0||toy<0||tox==301||toy==301)continue;
            if(place[tox][toy]==-1)place[tox][toy]=t;
            if(place[tox][toy]>t)place[tox][toy]=t;
        }
    }
    //bfs部分
    q.push(node(0,0,0));
    visit[0][0]=1;
    while(!q.empty()){
        node s=q.front();
        if(place[s.x][s.y]==-1){
            cout<<s.t<<endl;
            return 0;
        }
        int steps=s.t+1;
        for(int i=0;i<4;i++){
            int tox=s.x+dx[i];
            int toy=s.y+dy[i];
            if(tox<0||toy<0||visit[tox][toy])continue;
            if(place[tox][toy]!=-1&&steps>=place[tox][toy])continue;
            q.push(node(tox,toy,steps));
            visit[tox][toy]=1;
        }
        q.pop();
    }
    cout<<"-1"<<endl;
    return 0;
}