济源城乡建设局网站智能小程序开发平台

济源城乡建设局网站,智能小程序开发平台,做健康类网站怎么备案,在线oa免费crm题目描述贝西听说一场非凡的流星雨即将来临#xff1b;报告称这些流星将撞击地球并摧毁它们所碰到的任何东西。为了安全#xff0c;她发誓要找到一个安全的位置#xff08;一个从未被流星摧毁的地方#xff09;。她目前在坐标平面的原点放牧#xff0c;想要移动到一个新的…题目描述贝西听说一场非凡的流星雨即将来临报告称这些流星将撞击地球并摧毁它们所碰到的任何东西。为了安全她发誓要找到一个安全的位置一个从未被流星摧毁的地方。她目前在坐标平面的原点放牧想要移动到一个新的、更安全的位置同时避免在途中被流星摧毁。报告称将会有 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; }