题目描述 一场流星雨即将攻击地球，数量有限，共有M个陨石。若将地球看成一个N*N的方阵，陨石击中某个点时，会让该点及其上下左右四个点变成火海。有一个人站在点(1,1)处，每一分钟可以移动一步到相邻的上下左右四个格子，他不想被火海吞没，想要到达(N,N)的安全屋躲过灾难。请问他最短的逃命时间为多少，如果无论怎样都到达不了安全屋，则输出-1。

（注：安全屋被攻击不会变成火海。）

输入格式 第一行包含两个整数，分别为N和M。

第二至M+1行，每行包含三个整数X、Y、T，代表点(X,Y)将在第T分钟被陨石击中。

输出格式 仅包含一个整数，代表最短的逃命时间，如果无论怎样都到不了安全屋，则输出-1。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int mapp[3010][3010],n,m,vis[3010][3010],ans;//mapp[i][j]存如果有陨石那么存时间，如果没有存极大值
int xt[4]={0,0,1,-1};
int yt[4]={1,-1,0,0}; 
struct node{
	int x;
	int y;
	int step;
};
int bfs(int x,int y,int s){
	queue<node> q;
	node a;
	a.x=x;
	a.y=y;
	a.step=s;
	q.push(a);
	while(!q.empty()){
		int nx=q.front().x;
		int ny=q.front().y;
		int ns=q.front().step;
		q.pop();
		if(nx==n && ny==n){
			return ns;
		}
		ns++;
		for(int i=0;i<4;i++){
			int tx=nx+xt[i];
			int ty=ny+yt[i];
			if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]!=0||mapp[tx][ty]<=ns){
				continue;
			}
			vis[tx][ty]=1;
			node b;
			b.x=tx;
			b.y=ty;
			b.step=ns;
			q.push(b);
		}
	}
	return -1;
}
int main(){
     freopen("meteor.in","r",stdin);
     freopen("meteor.out","w",stdout);
	 cin>>n>>m;
	 
	 for(int i=1;i<=n;i++){
	 	for(int j=1;j<=n;j++){
	 		mapp[i][j]=1000000;
	 		vis[i][j]=0;
		 }
	 }
	int x;
	int y;
	int t;
	
	 for(int i=1;i<=m;i++){
	 	cin>>x>>y>>t;
         if(x!=n&&y!=n) mapp[x][y]=min(mapp[x][y],t);
         for(int j=0;j<4;j++){
         	if(x+xt[j]==n&&y+yt[j]==n){
            	continue;
            }
             else{
                 mapp[x+xt[j]][y+yt[j]]=min(mapp[x+xt[j]][y+yt[j]],t);
             }
         }
	 	
	 }
	 vis[1][1]=1;
	 cout<<bfs(1,1,0);
     fclose(stdin);
    fclose(stdout);
	 return 0;
}

U283553