题目描述
贝西听说一场非凡的流星雨即将来临；报告称这些流星将撞击地球并摧毁它们所碰到的任何东西。为了安全，她发誓要找到一个安全的位置（一个从未被流星摧毁的地方）。她目前在坐标平面的原点放牧，想要移动到一个新的、更安全的位置，同时避免在途中被流星摧毁。
报告称将会有 M 颗流星将会撞击，其中第 i 颗流星将在时间 Ti 撞击点 (Xi, Yi)。每颗流星会摧毁它撞击的点以及四个直线相邻的格点。
贝西在时间 0 从原点出发，可以在第一象限内以每秒一个距离单位的速度移动到任何尚未被流星摧毁的（通常是 4 个）相邻直线点。她在任何时间都不能位于被摧毁的点上。
确定贝西到达安全地点所需的最短时间。
输入格式
第一行一个整数M。
接下来M行，每行包含三个以空格分隔的整数：Xi, Yi 和 Ti。
输出格式
贝西到达安全地点所需的最短时间，或者如果不可能则输出 -1。
样例输入
4 0 0 2 2 1 2 1 1 2 0 3 5样例输出
5数据范围
1 <= M <= 50000,0 <= Xi <= 300,0 <= Yi <= 300,0 <= Ti <= 1000。
题解
#include <stdio.h> #include <stdlib.h> // 定义地图最大范围。虽然输入只有300，但冲击波会到301， // 且贝西可能需要绕路，所以开到405是安全的。 #define MAX_COORD 405 #define INF 99999999 // map[x][y] 存储该坐标变成焦土的最早时间 int map[MAX_COORD][MAX_COORD]; // visited[x][y] 标记是否已经访问过该点，防止BFS走回头路 int visited[MAX_COORD][MAX_COORD]; // 定义BFS队列的节点结构 typedef struct { int x; int y; int time; } Node; // 简单的队列实现 (静态数组足够大即可) Node queue[MAX_COORD * MAX_COORD]; int head = 0; int tail = 0; // 方向数组：上下左右 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int main() { int M; if (scanf("%d", &M) != 1) return 0; // 1. 初始化地图 // 默认所有点都是安全的（设为无限大） for (int i = 0; i < MAX_COORD; i++) { for (int j = 0; j < MAX_COORD; j++) { map[i][j] = INF; visited[i][j] = 0; // 0表示未访问 } } // 2. 读取流星数据，预处理地图危险时间 for (int i = 0; i < M; i++) { int x, y, t; scanf("%d %d %d", &x, &y, &t); // 更新流星中心点 // 只有当新的时间 t 比当前记录的时间更早时才更新 if (t < map[x][y]) { map[x][y] = t; } // 更新四个相邻点 for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; // 确保不越界 (只检查 >=0，上限由数组大小隐式保护，流星只砸到300) if (nx >= 0 && ny >= 0) { if (t < map[nx][ny]) { map[nx][ny] = t; } } } } // 3. 开始 BFS 寻找最短路径 // 特殊情况：如果起点在时刻0就被炸了，直接无法开始 if (map[0][0] == 0) { printf("-1\n"); return 0; } // 将起点加入队列 queue[tail].x = 0; queue[tail].y = 0; queue[tail].time = 0; tail++; visited[0][0] = 1; while (head < tail) { // 取出队首元素 Node curr = queue[head++]; // 【判断胜利条件】 // 如果当前点 map 值为 INF，说明这里永远不会被炸，就是安全点 if (map[curr.x][curr.y] == INF) { printf("%d\n", curr.time); return 0; } // 尝试往四个方向走 for (int i = 0; i < 4; i++) { int nx = curr.x + dx[i]; int ny = curr.y + dy[i]; int n_time = curr.time + 1; // 检查边界 if (nx >= 0 && ny >= 0 && nx < MAX_COORD && ny < MAX_COORD) { // 检查是否访问过 if (!visited[nx][ny]) { // 【核心逻辑】 // 只有当 "到达时间" < "该点被炸毁的时间" 时，才是安全的移动 if (n_time < map[nx][ny]) { visited[nx][ny] = 1; queue[tail].x = nx; queue[tail].y = ny; queue[tail].time = n_time; tail++; } } } } } // 如果队列空了还没找到安全点 printf("-1\n"); return 0; }
