题目链接：
解题报告：
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;}