链接：https://ac.nowcoder.com/acm/problem/207759 来源：牛客网

考古队员发现，牛市之所以会有那么多古老遗迹，是因为牛市曾经遭遇过一场几乎毁灭了他的流星雨，那场流星雨中流星体积很大，无法在撞击到地面前燃烧完，所以对牛市几乎造成了毁灭性的打击，但是，我们牛市的先民也是很厉害的，他们对于流星雨的预报虽然没有提前太多的时间但是详细到了每颗流星坠落的位置，所以虽然牛市在那一场流星雨之后满目疮痍，但是牛市的百姓大多都存活了下来。因为自然环境受到了巨大的破坏，他们记录下了这段历史搬到其他的地方繁衍生息，很多代人之后，牛市的自然环境有了恢复，他们后代中的一些人又搬了回来，逐渐建成了现在的牛市。这段历史被遗忘被尘封多年，但终于还是没有被遗忘……

根据遗迹中某个记载，当时先民们预报了一共有M颗流星（1≤M≤50,000）（1 \leq M \leq 50,000）（1≤M≤50,000）会坠落，他们将牛市划分成网格，他们预报其中第i颗流星会在时刻Ti(0≤Ti≤1,000)T_i(0 \leq T_i \leq 1,000)Ti(0≤Ti≤1,000)砸在坐标为(Xi,Yi)(0<=Xi<=300,0<=Yi<=300)(X_i, Y_i)(0 <= X_i <= 300,0 <= Y_i <= 300)(Xi,Yi)(0<=Xi<=300,0<=Yi<=300)的格子里。流星的力量会将它所在的格子，以及周围4个相邻的格子都化为焦土，在整个流星雨结束之前，这些格子都将无法行走站立。

现在有一个家族，在0时刻在0行0列的格子里，因为道路和建筑的原因，他们只能平行于坐标轴行动，每1个时刻，他们能移动到相邻的4个格子中的任意一个，当然这个格子要没有被撞击烧焦才行。（也就是说如果一个格子在时刻t被流星撞击或烧焦，那么他们只能在t之前的时刻在这个格子里出现。）

请你计算，这个家族是否在这场流星雨中幸存（移动到了一个没有被撞击或者烧焦的格子里一直待到流星雨结束），如果幸存，他们最少要花多少时间才移动到安全的格子里。

注：虽然流星只是砸在x，y坐标300的范围内，但是我们可以认为牛市在整个第一象限之内，即移动过程中x和y都可以超出300（但不能为负）。

做法：因为一个判断卡了一个小时的题，之后看了一下大佬的做法感觉泰强，于是写一个萌新做法供拷打。思路很好想，首先处理陨石坠落及其周围的格子，标上（最短）时间，因为可能后面的流星也会波及到之前的坑位，所以坑位的时间应该为第一次被毁坏的时间，我们把二维数组都标为-1，这样便于更新，如果初始位置没有被波及到，其实输出0就行，接着就去bfs，需要记录三个元素，x，y坐标和我走到这个位置的时间，然后开始往四个方向遍历。！！！！注意，当我们走到这个点的时间大于坑位的时间是应该跳过的，但是如果这个坑位始终是-1，不应该跳过！！！！卡了这个小时，差点道心破碎，然后找到一个是-1的点就好，因为是bfs，所以可以找到最近的可以生存的点，这题也没有管会不会越出最大边界，所以只看不到其他象限就好。

ps：不知道牛牛市有没有摧毁，但我快被摧毁了。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
struct node{
    int x,y,ti;
};
int timee[5010][5010];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[5010][5010];
void bfs()
{
    std::queue<node> q;
    node cur;
    cur.x=0,cur.y=0,cur.ti=0;
    q.push(cur);
     vis[0][0]=true;
    while(!q.empty())
    {
        node t=q.front();
        int x=t.x;
        int y=t.y;
        int ti=t.ti;
        ti++;
        q.pop();
       
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0];
            int dy=y+d[i][1];
           //ti++;
            if(dx<0||dy<0||(ti>=timee[dx][dy]&&timee[dx][dy]!=-1)||vis[dx][dy]==true) continue;
            // std::cout<<dx<<" "<<dy<<" "<<ti<<" "<<timee[dx][dy]<<endl;
            vis[dx][dy]=true;
            if(timee[dx][dy]==-1)
            {
                std::cout<<ti;
                return ;
            }
            node nxt;
            nxt.x=dx,nxt.y=dy,nxt.ti=ti;
            q.push(nxt);
        }
    }
    std::cout<<-1<<endl;
}
void slove()
{
     int n;
     std::cin>>n;
     for(int i=0;i<5010;i++)
     {  
        for(int j=0;j<5010;j++)
        {
            timee[i][j]=-1;
            vis[i][j]=false;
        }
     }
        while(n--)
     {
        int x,y,t;
        std::cin>>x>>y>>t;
        if(timee[x][y]==-1)
        {
            timee[x][y]=t;
        }
        else
        {
            timee[x][y]=std::min(timee[x][y],t);
        }
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0];
            int dy=y+d[i][1];
            if(dx<0||dy<0) continue; 
            if(timee[dx][dy]==-1)
            {
                timee[dx][dy]=t;
            }
            else
            {
                timee[dx][dy]=std::min(timee[dx][dy],t);
            }
        }
     }
   /* for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            printf("%4d",timee[i][j]);
        }
        printf("\n");
    }
    printf("\n");*/
     if(timee[0][0]==-1)
     {
        std::cout<<0<<endl;
         return ;
     }
     bfs();
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1;
    //std::cin>>T;
    while(T--)
    {
        slove();
    }

    return 0;
}