1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 方向数组定义 // 火的蔓延方向:8个方向(上下左右+四个对角线) int fire_dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int fire_dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 人的移动方向:4个方向(上下左右) int man_dx[] = {-1, 1, 0, 0}; int man_dy[] = {0, 0, -1, 1}; // [2] 全局常量与数组定义 const int MAXN = 105; const int INF = 0x3f3f3f3f; // 表示无穷大,代表格子永远不会着火 char mp[MAXN][MAXN]; // 存储原始地图 int fire_time[MAXN][MAXN]; // 每个格子的最早着火时间 int vis[MAXN][MAXN]; // 人的访问标记,避免重复走 int n, m; // 地图的行数n、列数m // [3] 人的BFS状态结构体:存储坐标和当前已走时间 struct Node { int x, y, time; }; int main() { // 关闭cin同步,加速输入 ios::sync_with_stdio(false); cin.tie(nullptr); // [4] 读取地图大小 cin >> n >> m; int sx, sy, ex, ey; // 起点S坐标(sx,sy)、终点T坐标(ex,ey) queue<pair<int, int>> fire_q; // 火灾多源BFS的队列 // [5] 初始化着火时间数组为无穷大,同时读取地图、定位起点终点和初始着火点 memset(fire_time, 0x3f, sizeof(fire_time)); for(int i = 0; i < n; i++) { cin >> mp[i]; for(int j = 0; j < m; j++) { if(mp[i][j] == 'S') // 起点 { sx = i; sy = j; } if(mp[i][j] == 'T') // 终点 { ex = i; ey = j; } if(mp[i][j] == 'F') // 初始着火点 { fire_time[i][j] = 0; // 初始着火时间为0 fire_q.push({i, j}); // 加入多源BFS队列 } } } // [6] 多源BFS:计算每个格子的最早着火时间 while(!fire_q.empty()) { auto cur = fire_q.front(); fire_q.pop(); int x = cur.first; int y = cur.second; // 遍历8个蔓延方向 for(int i = 0; i < 8; i++) { int nx = x + fire_dx[i]; int ny = y + fire_dy[i]; // 合法性校验:坐标在地图内,且新格子的着火时间可以更新为更早的时间 if(nx >= 0 && nx < n && ny >= 0 && ny < m && fire_time[nx][ny] > fire_time[x][y] + 1) { fire_time[nx][ny] = fire_time[x][y] + 1; fire_q.push({nx, ny}); } } } // [7] 人的BFS:求到终点的最短时间 memset(vis, 0, sizeof(vis)); queue<Node> man_q; // 起点初始化:时间0,标记已访问 man_q.push({sx, sy, 0}); vis[sx][sy] = 1; while(!man_q.empty()) { Node cur = man_q.front(); man_q.pop(); // 到达终点,直接输出当前时间,BFS保证这是最短时间 if(cur.x == ex && cur.y == ey) { cout << cur.time << endl; return 0; } // 遍历4个移动方向 for(int i = 0; i < 4; i++) { int nx = cur.x + man_dx[i]; int ny = cur.y + man_dy[i]; int new_time = cur.time + 1; // 合法性校验: // 1. 坐标在地图范围内 // 2. 该格子未被访问过 // 3. 到达该格子的时间 < 格子的着火时间(不会被烧到) if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && new_time < fire_time[nx][ny]) { vis[nx][ny] = 1; man_q.push({nx, ny, new_time}); } } } // [8] 队列遍历完毕仍未到达终点,无法安全到达,输出-1 cout << -1 << endl; return 0; }
- 1
信息
- ID
- 1311
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者