题意：Bessie去看流星，可是遇到了危险，流星落下砸毁上下左右中5个点，于是他就开始逃逃逃，Bessie开始在（0,0）点，每次可以向上下左右移动一步，每个流星落下都有一定的时间点，之后毁灭的点不可复原，问Bessie能逃脱危险的最短时间，不能逃出的话输出-1。
思路：在输入的时候进行预处理，一颗流星落下后，上下左右中5个点全毁灭，记录下最小的毁灭时间，如果不会被毁灭，则为-1。进行BFS，结构体记录下坐标（x，y）和到这一点的时间t，每次搜索上下左右中5个点，若毁灭时间小于等于当前时间，就说明此点已被毁灭，continue；若为-1，则为安全地点，BFS结束；若毁灭时间大于当前时间，说明此点目前可达，把这一点的时间记为目前时间，因为每一个点只能到达一次，之后再回来，情况更糟。
细节参见代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<map> #include<vector> #include<queue> #include<cmath> #include<algorithm> #include<sstream> #include<cstdlib> using namespace std; int dx[]={0,0,1,-1,0}; int dy[]={0,1,0,0,-1}; struct node{ int x; int y; int step; node(int xx=0,int yy=0,int ss=0):x(xx),y(yy),step(ss) {} }; int time[500][500]; int n,x,y,t; void BFS() { int x,y,t,xx,yy,ss; if(time[0][0]==0) {printf("-1\n");return ;} else if(time[0][0]==-1) {printf("0\n");return;} queue<node> Q; node beg(0,0,0); Q.push(beg); while(!Q.empty()){ node now=Q.front();Q.pop(); x=now.x; y=now.y; step=now.step; for(int i=0;i<5;i++){ xx=x+dx[i]; yy=y+dy[i]; ss=step+1; if(xx<0||yy<0) continue; if(time[xx][yy]<=ss&&time[xx][yy]!=-1) continue; if(time[xx][yy]==-1) {printf("%d\n",ss);return;} Q.push(node(xx,yy,ss)); time[xx][yy]=ss; } } printf("-1\n"); } int main() { scanf("%d",&n); memset(time,-1,sizeof(time)); for(int i=0;i<n;i++){ scanf("%d%d%d",&x,&y,&t); for(int j=0;j<5;j++){ int xx=x+dx[j]; int yy=y+dy[j]; if(xx<0||yy<0) continue; if(time[xx][yy]==-1) time[xx][yy]=t; else time[xx][yy]=min(time[xx][yy],t); } } BFS(); return 0; }