题意：有个小文青去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求小文青能否活命，如果能活命，最短的逃跑时间是多少？
分析：时间关联障碍，终点存在多个，终点不关联时间很关键。输入时就将最终可能的终点保存，搜索时判断每个点的否应该出现障碍（根据前一个点的时间）。
收获：最近在学BFS，这个题典型的障碍和终点都不确定，对重点和障碍的不确定的理解有收获。
但不知道为什么同样的代码 c++正确，G++会Re。。。
AC：
#include <iostream> #include <stdio.h> #include <map> #include <string.h> #include <queue> #include <algorithm> #include <stdlib.h> #include <math.h> using namespace std; class Node { public: int x; int y; int time; }; const int dx[]= {0,0,0,1,-1}; const int dy[]= {0,1,-1,0,0};//各个方向 int Map[310][310]; int bfs() { if(Map[0][0]==0) return -1; if(Map[0][0]==-1) return 0; queue<Node>que; Node now,q; q.x=q.y=q.time=0;//起点 que.push(q); while(que.size())//如果搜素不到需要的点 { q=que.front(); que.pop(); for(int i=1; i<5; i++)//因为向四个方向移动所以不用x=0，y=0 { now.x=q.x+dx[i]; now.y=q.y+dy[i]; now.time=q.time+1;//当前前进到的点的状态 if(now.x<0||now.x>=1001||now.y<0||now.y>=1001)//保证在题目规定的范围内 { continue; } if(Map[now.x][now.y]==-1) return now.time; if(now.time>=Map[now.x][now.y]) continue;//判断障碍在到达这个点之前是否出现 Map[now.x][now.y]=now.time;//走过的标记为障碍，保证不回头 que.push(now); } } return -1; } int main () { memset(Map,-1,sizeof(Map)); int n; scanf("%d",&n); while(n--) { int x,y,t; scanf("%d%d%d",&x,&y,&t); for(int i=0; i<5; i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(Map[nx][ny]==-1) { Map[nx][ny]=t; } else { if(Map[nx][ny]>t)//优先选取时间早的陨石 { Map[nx][ny]=t; } } } } cout << bfs(); }
