题目描述
在公元\(114514\)年小朱在学校里上课,突然听见学校广播播放一条骇人听闻的消息:一群陨石将袭击我市,由于陨石积过大数量多，它们无法在撞击到地面前燃烧 殆尽,将会对它撞到的一切东西造成毁灭性的打击。
小朱同志开始担心自己的 安全问题。他一定要在被流星砸到前，到达一个安全的地方 （也就是说，一块不会被任何流星砸到的土 地）。如果将我市放入一个直角坐标系中， 小朱同志现在的位置是原点，并且，小朱同志不能踏上一块被流星砸过的土地。
根据预 报，一共有\(M\)颗流星\((1<=M<=50,000)\)会坠落在我市上，其中第\(i\)颗流星会在时刻 \(Ti\)\((0<=Ti<=1,000)\)砸在坐标为\((Xi,Yi)\)\((0<=Xi<=300；0<=Yi<=300)\)的格子里。流星的力量会将它所在的格子，以及周围\(4\)个相邻的格子都化为焦土，当然 小朱同志也无法再在这些 格子上行走。
小朱同志在时刻\(0\)开始行动，它只能在第一象限中， 平行于坐标轴行动，每\(1\)个时刻中，他能移动到相邻的（一般是\(4\)个）格子中的任意一个， 当然目标格子要没有被烧焦才行。如果一个格子在时刻\(t\)被流星撞击或烧焦，那么小朱同志 只能在\(t\)之前的时刻在这个格子里出现。
请你计算一下，小朱同志最少需要多少时间才能到 达一个安全的格子。
输入格式
第\(1\)行: \(1\)个正整数：\(M\)
第\(2...M+1\)行:
第\(i+1\)行为\(3\)个用空格隔开的整数：\(Xi\)，\(Yi\)，以及\(Ti\)
输出格式
输出1个整数，即小朱同志逃生所花的最少时间。
如果小朱同志无论如何都无法在陨石坠落中存活下来，输出 -1
样例
输入样例
5
0 0 2
2 1 3
1 1 3
0 2 3
8 9 0
输出样例
3
Tips:
输入说明:
一共有\(4\)颗流星将坠落在霸中，它们落地点的坐标分别是\((0,0)\)，(2,1)，$(2,1) \(，\)(1,1)$ 以及\((0,3)\)，时刻分别为\(2\)，\(2\)，2，\(2\)，\(5\)。
\(AC\)代码:
/*****************
备注：
*****************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
#define LL long long
#define MAXM 3010
#define MAXN 3010
const int N =300+10;
const int INF =0x3f3f3f3f;
int m,x,y,t,a[N][N];
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
bool v[N][N];
struct node
{
int x,y,num;
};
queue<node> q;
void bfs()
{
q.push((node){0,0,0});
v[0][0]=1;
while(!q.empty())
{
node top=q.front();
q.pop();
if(a[top.x][top.y]==-1)
{
cout<<top.num;
exit(0);
}
for(int i=1;i<=4;i++)
{
int xx=top.x+dx[i];
int yy=top.y+dy[i];
if(xx>=0 && yy>=0 && (a[xx][yy]==-1 || a[xx][yy]>top.num+1)&& v[xx][yy]==0)
{
q.push((node){xx,yy,top.num+1});
v[xx][yy]=1;
}
}
}
}
int main ()
{
memset(a,-1,sizeof(a));
cin>>m;
while(m--)
{
cin>>x>>y>>t;
for(int i=0;i<5;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=0 && yy>=0 &&(a[xx][yy]==-1 || a[xx][yy]>t))
a[xx][yy]=t;
}
}
bfs();
cout<<-1;
return 0;
}