🔥 逃离火灾

📝 题目描述

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

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

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

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

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

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

📋 代码模板

javatypescript

java

class Solution {
    public int maximumMinutes(int[][] grid) {

    }
}

typescript

function maximumMinutes(grid: number[][]): number {
    
}

💡 提示

$m = g r i d . l e n g t h$
$n = g r i d [i] . l e n g t h$
$2 \leq m \leq 300$
$2 \leq n \leq 300$
$4 \leq m \cdot n \leq 2 \cdot 10^{4}$
$g r i d [i] [j]$ 是0，1或者2
$g r i d [0] [0] == g r i d [m - 1] [n - 1] == 0$

🚀 示例

示例一

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。

示例一

示例二

grid输入为[[0,0,0,0],[0,1,2,0],[0,2,0,0]]。在该网格上，人无论怎么向外移动，都会被火烧到，因此答案为-1。

示例二

示例三

grid输入为[[0,0,0],[2,2,0],[1,2,0]]。在该网格上，火会被墙围住，永远蔓延不出来，因此答案为1000000000。

示例三

🖊️ 题解

二分查找 + BFS

假设人在初始位置停留 $t$ 分钟后能够顺利到达安全屋，那么人一定可以在初始位置停留 $< t$ 分钟，相反，如果人在初始位置停留 $t$ 分钟后不能顺利到达安全屋，那么人也一定不可以在初始位置停留 $> t$ 分钟。根据该单调性，本题可以利用二分查找来得到在成功到达安全屋的前提下，人能够在初始位置停留的最大分钟数 $a n s w e r$ 。

单调性

二分查找的下限可以设置为 $0$ ，这是因为人可以一刻都不停留。而二分查找的上限可以设置为 $m \cdot n$ ，这是因为火势最多在不超过网格大小的时间内完全蔓延。

那么我们如何来验证人在停留 $t$ 分钟后，其是否能够安全到达网格的右下角呢？火势蔓延的过程可以使用BFS算法实现，为了避免被火烧到，人需要用最短的时间到达安全屋，这同样可以用BFS算法实现。如果在相同时间点，人和火相遇，那么人就会被火烧到。但根据题意，如果相遇的格子是右下角（安全屋），这种情况将被视为人安全。因此，我们需要创建两个布尔数组： $o n F i r e$ 和 $p a s s B y$ ，分别表示网格单元格“是否着火”和“人是否经过”。起初，利用BFS让火势向外扩散 $t$ 轮。其次，通过BFS不断模拟在同一轮中，人先移动，火再蔓延。如果下一分钟人的格子出队时，发现格子已经被火烧到了，就可直接跳过，因为同一时间人和火相遇，人会被烧到。如果当前分钟人到达了右下角， $c h e c k$ 函数可直接返回 $t r u e$ ，因为即使火在同一轮中到达了右下角，人仍然被视为安全。最后，BFS结束，人已经没有格子可走， $c h e c k$ 函数返回 $f a l s e$ 。

在BFS过程中，人不能走“超出网格范围”、“已经着火”、“已经走过”、“表示墙”的单元格，火不能向“超出网格范围”、“已经着火”、“表示墙”的单元格蔓延。

需要注意的是，如果最后二分查找得到的答案是 $m \cdot n$ ，则表明存在一条安全路径，火永远烧不到人。因此，在这种情况下，根据题意，本题的答案应为 $10^{9}$ 。

javatypescript

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int FIRE = 1;
    private final static int GRASS = 0;

    public int maximumMinutes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int low = 0, high = m * n;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (check(grid, mid)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high == m * n ? (int) 1e9 : high;
    }

    private boolean check(int[][] grid, int t) {
        int m = grid.length, n = grid[0].length;
        boolean[][] onFire = new boolean[m][n];
        Queue<int[]> fireQueue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == FIRE) {
                    fireQueue.offer(new int[]{i, j});
                    onFire[i][j] = true;
                }
            }
        }
        spreadFire(grid, onFire, fireQueue, t);
        boolean[][] passBy = new boolean[m][n];
        Queue<int[]> personQueue = new LinkedList<>();
        personQueue.offer(new int[]{0, 0});
        passBy[0][0] = true;
        while (!personQueue.isEmpty()) {
            int size = personQueue.size();
            while (size > 0) {
                size--;
                int[] cell = personQueue.poll();
                int oldI = cell[0], oldJ = cell[1];
                if (onFire[oldI][oldJ]) {
                    continue;
                }
                for (int d = 0; d < 4; d++) {
                    int i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                    if (!inRange(grid, i, j) || onFire[i][j] || passBy[i][j] || grid[i][j] != GRASS) {
                        continue;
                    }
                    if (i == m - 1 && j == n - 1) {
                        return true;
                    }
                    personQueue.offer(new int[]{i, j});
                    passBy[i][j] = true;
                }
            }
            spreadFire(grid, onFire, fireQueue, 1);
        }
        return false;
    }

    private void spreadFire(int[][] grid, boolean[][] onFire, Queue<int[]> fireQueue, int t) {
        while (!fireQueue.isEmpty() && t > 0) {
            int size = fireQueue.size();
            while (size > 0) {
                int[] cell = fireQueue.poll();
                int oldI = cell[0], oldJ = cell[1];
                for (int d = 0; d < 4; d++) {
                    int i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                    if (inRange(grid, i, j) && grid[i][j] == GRASS && !onFire[i][j]) {
                        fireQueue.offer(new int[]{i, j});
                        onFire[i][j] = true;
                    }
                }
                size--;
            }
            t--;
        }
    }

    private boolean inRange(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

typescript

const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const GRASS = 0, FIRE = 1;

function maximumMinutes(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const inRange = (i: number, j: number) => {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    const check = (t: number): boolean => {
        const onFire: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
        const fireQueue: number[][] = [];
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] == FIRE) {
                    fireQueue.push([i, j]);
                    onFire[i][j] = true;
                }
            }
        }
        const spreadFire = (t: number): void => {
            while (fireQueue.length > 0 && t > 0) {
                let size = fireQueue.length;
                while (size > 0) {
                    const cell: number[] = fireQueue.shift()!;
                    const oldI = cell[0], oldJ = cell[1];
                    for (let d = 0; d < 4; d++) {
                        const i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                        if (inRange(i, j) && grid[i][j] == GRASS && !onFire[i][j]) {
                            fireQueue.push([i, j]);
                            onFire[i][j] = true;
                        }
                    }
                    size--;
                }
                t--;
            }
        }
        spreadFire(t);
        const passBy: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
        const personQueue: number[][] = [];
        personQueue.push([0, 0]);
        passBy[0][0] = true;
        while (personQueue.length > 0) {
            let size = personQueue.length;
            while (size > 0) {
                size--;
                const cell: number[] = personQueue.shift()!;
                const oldI = cell[0], oldJ = cell[1];
                if (onFire[oldI][oldJ]) {
                    continue;
                }
                for (let d = 0; d < 4; d++) {
                    const i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                    if (!inRange(i, j) || passBy[i][j] || onFire[i][j] || grid[i][j] != GRASS) {
                        continue;
                    }
                    if (i == m - 1 && j == n - 1) {
                        return true;
                    }
                    personQueue.push([i, j]);
                    passBy[i][j] = true;
                }
            }
            spreadFire(1);
        }
        return false;
    }
    let low = 0, high = m * n;
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (check(mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return high == m * n ? 1e9 : high;
}

BFS + 分类讨论

将网格中的一个草地格子记为 $G$ ，设人最快在 $t_{1}$ 分钟到达 $G$ ，火最快在 $t_{2}$ 分钟到达 $G$ 。如果人比火先到达 $G$ ，则说明 $t_{1} < t_{2}$ ，且人在到达 $G$ 的中途不会被火烧到，因为人在最快到达 $G$ 的路线上，火永远比人慢。若火到不了 $G$ ， $t_{2}$ 可以理解为 $\infty$ 。

人不会被火烧到

火和人不能在草地同时相遇，那如果 $G$ 是安全屋，答案就是 $t 2 - t 1 - 1$ 吗？这个结论是不准确的，题目将人和火同时在安全屋相遇的情况是视为安全的，而又由于火可能是沿着其他路径烧到安全屋的，因此人在等待 $1$ 分钟后，其在到达安全屋的路线上可能也不会被火烧到。

应少等待1分钟

在以上这种特殊情况下，人可以在初始位置最多等待 $t 2 - t 1$ 分钟。因此，我们可以通过BFS求出人到每个草地格子的最短时间 $p e r s o n T i m e$ ，以及火到每个草地格子的最短时间 $f i r e T i m e$ ，如果到不了，可以将其值设置为 $- 1$ ，并进行如下分类讨论。

如果 $p e r s o n T i m e [m - 1] [n - 1] = - 1$ ，则说明人无法到达安全屋，返回 $- 1$ 。
否则，如果 $f i r e T i m e [m - 1] [n - 1] = - 1$ ，则说明火无法到达安全屋，而由于此时人和安全屋是连通的，火和安全屋又不是连通的，因此人和火是不连通的，火永远烧不到人，人可以在初始位置无限等待下去，返回 $10^{9}$ 。
否则，记 $d i s = f i r e T i m e [m - 1] [n - 1] - p e r s o n T i m e [m - 1] [n - 1]$ 。
如果 $d i s < 0$ ，说明火比人先到安全屋，返回 $- 1$ 。
如果 $d i s \geq 0$ ，判断人能否在初始位置停留 $d i s$ 分钟后，先比火到达安全屋左边或上边的相邻格子。如果可以，返回 $d$ ，相反，返回 $d - 1$ 。

javatypescript

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int NOT_VISITED = -1;
    private final static int GRASS = 0, FIRE = 1;

    public int maximumMinutes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        List<int[]> personStart = new ArrayList<>(), fireStart = new ArrayList<>();
        personStart.add(new int[]{0, 0});
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == FIRE) {
                    fireStart.add(new int[]{i, j});
                }
            }
        }
        int[][] personTime = bfs(grid, personStart), fireTime = bfs(grid, fireStart);
        if (personTime[m - 1][n - 1] == NOT_VISITED) {
            return -1;
        }
        if (fireTime[m - 1][n - 1] == NOT_VISITED) {
            return (int) 1e9;
        }
        int dis = fireTime[m - 1][n - 1] - personTime[m - 1][n - 1];
        if (dis < 0) {
            return -1;
        }
        int fireTop = fireTime[m - 2][n - 1], fireLeft = fireTime[m - 1][n - 2];
        int personTop = personTime[m - 2][n - 1], personLeft = personTime[m - 1][n - 2];
        if ((fireTop != NOT_VISITED && personTop + dis < fireTop) ||
                (fireLeft != NOT_VISITED && personLeft + dis < fireLeft)) {
            return dis;
        }
        return dis - 1;
    }

    private int[][] bfs(int[][] grid, List<int[]> start) {
        int m = grid.length, n = grid[0].length;
        int[][] time = new int[m][n];
        for (int[] t : time) {
            Arrays.fill(t, NOT_VISITED);
        }
        Queue<int[]> queue = new LinkedList<>();
        for (int[] s : start) {
            queue.offer(s);
            time[s[0]][s[1]] = 0;
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int oldI = cell[0], oldJ = cell[1];
            for (int d = 0; d < 4; d++) {
                int i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                if (i < 0 || i > m - 1 || j < 0 || j > n - 1
                        || time[i][j] != NOT_VISITED || grid[i][j] != GRASS) {
                    continue;
                }
                queue.offer(new int[]{i, j});
                time[i][j] = time[oldI][oldJ] + 1;
            }
        }
        return time;
    }
}

typescript

const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const NOT_VISITED = -1;
const GRASS = 0, FIRE = 1;

function maximumMinutes(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const bfs = (start: number[][]): number[][] => {
        const time: number[][] = Array.from({length: m}, () => Array(n).fill(NOT_VISITED));
        const queue: number[][] = [];
        for (const s of start) {
            queue.push(s);
            time[s[0]][s[1]] = 0;
        }
        while (queue.length > 0) {
            const cell: number[] = queue.shift()!;
            const oldI = cell[0], oldJ = cell[1];
            for (let d = 0; d < 4; d++) {
                const i = oldI + DIRS[d][0], j = oldJ + DIRS[d][1];
                if (i < 0 || i > m - 1 || j < 0 || j > n - 1
                    || time[i][j] != NOT_VISITED || grid[i][j] != GRASS) {
                    continue;
                }
                queue.push([i, j]);
                time[i][j] = time[oldI][oldJ] + 1;
            }
        }
        return time;
    }
    const personStart: number[][] = [[0, 0]], fireStart: number[][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == FIRE) {
                fireStart.push([i, j]);
            }
        }
    }
    const personTime = bfs(personStart), fireTime = bfs(fireStart);
    if (personTime[m - 1][n - 1] == NOT_VISITED) {
        return -1;
    }
    if (fireTime[m - 1][n - 1] == NOT_VISITED) {
        return 1e9;
    }
    const dis = fireTime[m - 1][n - 1] - personTime[m - 1][n - 1];
    if (dis < 0) {
        return -1;
    }
    const fireTop = fireTime[m - 2][n - 1], personTop = personTime[m - 2][n - 1];
    const fireLeft = fireTime[m - 1][n - 2], personLeft = personTime[m - 1][n - 2];
    if ((fireTop != NOT_VISITED && personTop + dis < fireTop)
        || (fireLeft != NOT_VISITED && personLeft + dis < fireLeft)) {
        return dis;
    }
    return dis - 1;
}

💭 复杂度分析

基于二分查找 + BFS的解决方案的复杂度分析如下。

时间复杂度： $O (m n \cdot \log m n)$ ，其中 $m$ 和 $n$ 分别为 $g r i d$ 的行数和列数。二分查找循环 $\log m n$ 次，每次check的时间复杂度为 $m n$ 。
空间复杂度： $O (m n)$ 。

基于BFS + 分类讨论的解决方案的复杂度分析如下。

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别为 $g r i d$ 的行数和列数。
空间复杂度： $O (m n)$ 。

🔥 逃离火灾 ​

📝 题目描述 ​

📋 代码模板 ​

💡 提示 ​

🚀 示例 ​

示例一 ​

示例二 ​

示例三 ​

🖊️ 题解 ​

二分查找 + BFS ​

BFS + 分类讨论 ​

💭 复杂度分析 ​

🔥 逃离火灾

📝 题目描述

📋 代码模板

💡 提示

🚀 示例

示例一

示例二

示例三

🖊️ 题解

二分查找 + BFS

BFS + 分类讨论

💭 复杂度分析