• LeetCode 2258. 逃离火灾：BFS

    【LetMeFly】2258.逃离火灾

    力扣题目链接：https://leetcode.cn/problems/escape-the-spreading-fire/

    给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

    • 0 表示草地。
    • 1 表示着火的格子。
    • 2 表示一座墙，你跟火都不能通过这个格子。

    一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。

    请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。

    注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

    如果两个格子有共同边，那么它们为 相邻 格子。

     

    示例 1：

    输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出：3
解释：上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。

    示例 2：

    输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出：-1
解释：上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
所以返回 -1 。

    示例 3：

    输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
输出：1000000000
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 109 。

     

    提示：

    • m == grid.length
    • n == grid[i].length
    • 2 <= m, n <= 300
    • 4 <= m * n <= 2 * 104
    • grid[i][j] 是 0 ，1 或者 2 。
    • grid[0][0] == grid[m - 1][n - 1] == 0

    方法一：二分 + BFS

    首先以所有的🔥为起点开始广度优先搜索，这样我们就能得到“火焰燃烧图”（🔥燃烧到某个坐标所需耗时）。

    接着可以二分“👱的开局等待时长”。假设开局等待时间为 t t t，那么就从时间 t t t开始对👱能到达的位置进行广度优先搜索。

    在对👱的广搜过程中：

    • 若搜索到了“安全屋”的位置：若“👱的到达耗时小于等于🔥的到达耗时”，则表示👱能等待时间 t t t后再出发
    • 否则（非安全屋位置）：若“👱的到达耗时小于🔥的到达耗时”，则表示人能到达该位置

    以上，即可。

    • 时间复杂度 O ( m n log ⁡ m n ) O(mn\log mn) O(mnlogmn)，其中 s i z e ( g r i d ) = m × n size(grid)=m\times n size(grid)=m×n
    • 空间复杂度 O ( m n ) O(mn) O(mn)

    AC代码

    C++
    class Solution {
private:
    int m, n;
    int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    vector<vector<int>> fireTime;
    void debug(vector<vector<int>>& v) {
        for (auto& t : v) {
            for (auto& tt : t) {
                cout << tt << ' ';
            }
            cout << endl;
        }
    }

    void bfsFire(vector<vector<int>>& grid) {  // 计算火燃烧到每个位置时所需耗时并存入fireTime
        vector<vector<int>> graph = grid;
        fireTime = vector<vector<int>>(m, vector<int>(n, 1e9));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    q.push({i, j});
                    fireTime[i][j] = 0;
                }
            }
        }
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = x + direction[d][0];
                int ty = y + direction[d][1];
                if (tx >= 0 && tx < m && ty >= 0 && ty < n && !graph[tx][ty]) {
                    graph[tx][ty] = 1;
                    fireTime[tx][ty] = fireTime[x][y] + 1;
                    q.push({tx, ty});
                }
            }
        }
    }

    bool check(vector<vector<int>>& grid, int t) {  // 其实是bfsPeople
        vector<vector<int>> peopleTime(m, vector<int>(n, 0)), graph(grid);
        peopleTime[0][0] = t;
        queue<pair<int, int>> q;
        q.push({0, 0});
        graph[0][0] = 2;
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = x + direction[d][0];
                int ty = y + direction[d][1];
                int toTime = peopleTime[x][y] + 1;
                if (tx >= 0 && tx < m && ty >= 0 && ty < n && !graph[tx][ty]) {
                    graph[tx][ty] = 2;
                    if (tx == m - 1 && ty == n - 1 && toTime <= fireTime[m - 1][n - 1]) {
                        return true;
                    }
                    if (toTime < fireTime[tx][ty]) {
                        peopleTime[tx][ty] = toTime;
                        q.push({tx, ty});
                    }
                }
            }
        }
        return false;
    }
public:
    int maximumMinutes(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        bfsFire(grid);
        int l = 0, r = n * m;
        int ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (check(grid, mid)) {
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return ans >= n * m ? 1e9 : ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    Python
    # from typing import List
# from copy import deepcopy

class Solution:
    def __init__(self) -> None:
        self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    
    def bfsFire(self, grid: List[List[int]]) -> None:
        fireTime = [[int(1e9)] * self.n for _ in range(self.m)]
        graph = deepcopy(grid)
        q = []
        for i in range(self.m):
            for j in range(self.n):
                if graph[i][j] == 1:
                    q.append((i, j))
                    fireTime[i][j] = 0
        while q:
            x, y = q[0]
            q = q[1:]
            for dx, dy in self.direction:
                tx, ty = x + dx, y + dy
                if tx >= 0 and tx < self.m and ty >= 0 and ty < self.n and not graph[tx][ty]:
                    q.append((tx, ty))
                    fireTime[tx][ty] = fireTime[x][y] + 1
                    graph[tx][ty] = 1
        self.fireTime = fireTime
    
    def check(self, grid: List[List[int]], t: int) -> bool:
        if t == 4:
            print(self.fireTime)
        peopleTime = [[0] * self.n for _ in range(self.m)]
        graph = deepcopy(grid)
        q = []
        q.append((0, 0))
        graph[0][0] = 2
        peopleTime[0][0] = t
        while q:
            x, y = q[0]
            q = q[1:]
            thisTime = peopleTime[x][y] + 1
            for dx, dy in self.direction:
                tx, ty = x + dx, y + dy
                if tx >= 0 and tx < self.m and ty >= 0 and ty < self.n and not graph[tx][ty]:
                    graph[tx][ty] = 2
                    if tx == self.m - 1 and ty == self.n - 1 and thisTime <= self.fireTime[-1][-1]:
                        return True
                    if thisTime < self.fireTime[tx][ty]:
                        peopleTime[tx][ty] = thisTime
                        q.append((tx, ty))
        return False

    def maximumMinutes(self, grid: List[List[int]]) -> int:
        self.m, self.n = len(grid), len(grid[0])
        self.bfsFire(grid)
        l, r = 0, self.m * self.n
        ans = -1
        while l <= r:
            mid = (l + r) // 2
            if self.check(grid, mid):
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return int(1e9) if ans >= self.m * self.n else ans

if __name__ == '__main__':
    print(Solution().maximumMinutes(
        [[0,2,0,0,0,0,0],
         [0,0,0,2,2,1,0],
         [0,2,0,0,1,2,0],
         [0,0,2,2,2,0,2],
         [0,0,0,0,0,0,0]])
    )
    """
    [[6, ∞, 4, 3, 2, 1, 2],
     [5, 4, 3, ∞, ∞, 0, 1],
     [6, ∞, 2, 1, 0, ∞, 2],
     [7, 8, ∞, ∞, ∞, 14, ∞],
     [8, 9, 10, 11, 12, 13, 14]]
    """

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    方法二：数次BFS（无代码，可忽略）

    其实这道题特殊的一点只有“安全屋”，只有安全屋这里🔥和👱可以同时到达。其他位置都必须保证👱比🔥严格地优先到达。

    怎么到安全屋呢？要么从安全屋的左边，要么从安全屋的上面。因此先BFS一下得到🔥的“燃烧耗时图”，再按从 0 0 0时刻出发BFS👱。

    最后判断一下安全屋及其左上两个位置👱🔥的到达时间，即可推断出👱在起点最多待多久。

    因 2 15 > 2 × 1 0 4 2^{15}>2\times10^4 215>2×104，故方法一中也不会二分太多次。

    同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
    Tisfy：https://letmefly.blog.csdn.net/article/details/134331955

  • 相关阅读:
    通用接口开放平台设计与实现——番外篇1 通用接口平台与开发平台关系的思考
    基于Mybatis及Mybatis-Plus的多数据源解决方案
    美团三面：让你怀疑人生的Spring Boot夺命连环40问
    人体呼吸存在传感器成品，毫米波雷达探测感知技术，引领智能家居新潮流
    帮你搜遍GitHub！一次性解决面试中常见并发编程问题，附笔记合集
    分期付款中的利率问题
    python毕业设计题目推荐汽车销售系统
    Proteus仿真--1602LCD显示仿手机键盘按键字符（仿真文件+程序）
    力扣随机一题 哈希表 排序 数组
    ASEMI代理艾赛斯二极管DSA300I100NA，肖特基DSA300I100NA
  • 原文地址：https://blog.csdn.net/Tisfy/article/details/134331955