1 条题解

  • 0
    @ 2026-2-17 22:18:59
    #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
    上传者