题意：Bessie被流星雨袭击，给出m颗流星，每个流星都有坠落的横纵坐标，以及坠落的时间。每个流星坠落后，该格子连同上、下、左、右四个格子都不能走了。Bessie从（0，0）出发，每次只能向上、下、左、右移动一格，求达到安全位置的最小移动次数，不能则输出-1。
思路：地图的大小没有上限，陨石的坐标范围只到300，所以无解的情况只有两种：1、通往安全区域的路线被掉下的流星阻挡。2、（0，0）位置在0时刻被流星砸中，这个情况要注意一下。
预处理流星过后的地图，标记出安全点，毁掉的区域记录最早被砸毁的时间，这个时间以后该点就不能走了。之后bfs的时候增加一个变量记录时间就行了。
因为搜索范围判断只写到300WA了一发，唉长记性了。
#include<cmath> #include<cstdio> #include<queue> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f typedef long long LL; typedef pair<int,int> P; #define N 350 int d[2][4]={-1,0,1,0,0,-1,0,1}; int g[N][N],step[N][N]; int main(){ int x,y,t,m; scanf("%d",&m); memset(g,0x3f,sizeof(g));//初始化成INF for(int i=0;i<m;++i){ scanf("%d%d%d",&x,&y,&t); if(g[x][y]>t)g[x][y]=t; for(int i=0;i<4;++i){//g保存每个点最早被炮击的时间，没有则为INF int dx=x+d[0][i],dy=y+d[1][i]; if(dx>=0&&dx<=310&&dy>=0&&dy<=310&&g[dx][dy]>t){ g[dx][dy]=t; } } } int ans=-1; if(g[0][0]){ memset(step,-1,sizeof(step));//到这一格的最小步长，-1表示没走过 step[0][0]=0; queue<P> q; q.push(P(0,0)); while(q.size()){ if(ans!=-1)break; P p=q.front(); q.pop(); x=p.first,y=p.second; if(g[x][y]==INF){//找到安全点 ans=step[x][y]; break; } for(int i=0;i<4;++i){ int dx=x+d[0][i],dy=y+d[1][i]; if(dx>=0&&dx<=310&&dy>=0&&dy<=310&&g[dx][dy]>(step[x][y]+1)&&step[dx][dy]==-1){//这里的范围要比300大！！ step[dx][dy]=step[x][y]+1; q.push(P(dx,dy)); } } } } printf("%d\n",ans); }
