题目链接：

解题报告：

1、流星坠落的点，四周和自己本身都被毁灭，不断更新每个点被毁灭的时候的最短时间。

2、搜索终点是，到达某个点，这个不会有流星毁灭他，即他的毁灭的时间大于最后一个流星到达时的时间。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAX 302        ///地图宽度int m;    ///流星数int map[MAX][MAX];    ///地图bool visited[MAX][MAX];    ///是否访问过int last;    ///最晚的流星时间int go[][2] ={
   {
   1,0},{-1,0},{
   0,1},{
   0,-1},{
   0,0}}; ///五个方向struct Meteor{    int x;    int y;    int t;}meteor[50000];    ///流星结构typedef Meteor Node;    ///节点结构，用于bfsint max(int a, int b){    return a > b ? a : b;}int bfs(){    memset(visited, false, sizeof(visited));    queue
        
          q;    ///队列    Node fir;    ///起始点入队    fir.x = fir.y = fir.t = 0;    visited[0][0] = true;    q.push(fir);    while (!q.empty())    ///bfs    {        Node now = q.front();        q.pop();        for (int i = 0; i < 4; i++)    ///每次必须行动1格        {            Node tmp = now;            tmp.x += go[i][0];            tmp.y += go[i][1];            tmp.t++;            if (tmp.x >= 0 && tmp.y >= 0 && map[tmp.x][tmp.y]>tmp.t && !visited[tmp.x][tmp.y])    ///没越界、流星还未砸这个格子、还没访问过(重复访问就是不是bfs最优解了)            {                visited[tmp.x][tmp.y] = true;    ///标记                if (map[tmp.x][tmp.y] > last)    ///如果格子不会被砸到                {                    return tmp.t;                }                q.push(tmp);            }        }    }    return -1;}int main(){    while (scanf("%d", &m) != EOF)    {        for (int i = 0; i < m; i++)        {            scanf("%d%d%d", &meteor[i].x, &meteor[i].y, &meteor[i].t);        }        memset(map, 0x7f, sizeof(map));    ///要严谨一点可以用0x7fffffff，不过就不能用memset了        for (int i = 0; i < m; i++)        {            ///计算最晚流星的时间            if (i == 0)                last = meteor[i].t;            else                last = max(last, meteor[i].t);            ///更新地图上某个点的最快的流星下落时间            for (int j = 0; j < 5; j++)            {                int tx = meteor[i].x + go[j][0];                int ty = meteor[i].y + go[j][1];                if (tx >= 0 && ty >= 0 && map[tx][ty]>meteor[i].t)                {                    map[tx][ty] = meteor[i].t;                }            }        }        if (map[0][0] == 0)    ///起始点被砸直接gg            printf("-1\n");        else  ///否则bfs            printf("%d\n", bfs());    }    return 0;}