2258. 逃离火灾 : 详解如何从「二分」到「分类讨论」(图解过程)-六虎

题目描绘

这是 LeetCode 上的 2258. 逃离火灾 ，难度为困难。

Tag : 「多源 BFS」、「二分」、「预处理」

给你一个下标从 0 开端巨细为 m x n 的二维整数数组 grid，它表明一个网格图。

每个格子为下面 $3$ 个值之一：

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

一开端你在最左上角的格子 $(0, 0)$ ，你想要抵达最右下角的安全屋格子 $(m - 1, n - 1)$ 。

每一分钟，你能够移动到相邻的草地格子。

每次你移动之后，着火的格子会分散到一切不是墙的相邻格子。

请你回来你在初始方位能够逗留的最多分钟数，且逗留完这段时刻后你还能安全抵达安全屋。

假如无法完成，请你回来 $- 1$ 。假如不管你在初始方位逗留多久，你总是能抵达安全屋，请你回来 $10^9$ 。

留意，假如你抵达安全屋后，火立刻到了安全屋，这视为你能够安全抵达安全屋。

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

示例 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 = g r i d . l e n g t h$
$n = g r i d [i] . l e n g t h$
$2 <= m, n <= 300$
$10^4$
grid[i][j] 是 0，1 或许 2。
$g r i d [0] [0] = g r i d [m - 1] [n - 1] = 0$

二分 + BFS

火势延伸是一个固定的进程，只要人员移动需求决议计划。

假定人员最晚在 $t$ 秒后动身，仍能抵达安全屋，阐明人员对逃走道路的拜访，要比火势更快。那么人员在更早的时刻点（ $[0, t - 1]$ 秒后）动身，必定仍能按照原定道路抵达安全屋（火势对途径的影响不变）。

因而，在以 $t$ 为切割点的（正整数）数轴上，具有二段性，可运用「二分」求切割点。

假定存在某个断定函数 check，用于检查人员在 $x$ 秒后动身能否抵达安全屋，那么可知：

当实践推迟动身的秒数，小于等于 $t$ 秒，必定能安全抵达
当实践推迟动身的描绘，超过 $t$ 秒，必定不能安全抵达

在人员移动道路中，“回头路”是没有意义的，因而人员对每个点的拜访次数最多为一次。一起，不考虑墙的阻拦，火势也最多在不超过棋盘巨细的时刻内彻底延伸。

这辅导咱们最大推迟动身时刻不会超过 $n m$ ，可在 $[0, n m]$ 值域内进行二分。

接下来，考虑怎么完成 check 函数，函数入参为推迟动身秒数 $t$ ，回来值为推迟动身后能否抵达安全屋。

首先，关于一般方位，假如火势和人员一起抵达，是不答应的，而安全屋 $(n - 1, m - 1)$ 方位的一起抵达，是答应的。

因而，咱们需求运用两个二维数组 fg 和 pg 别离记录「火势」和「人员」抵达某个方位的最早时刻。

创建用于模仿火势延伸的行列 fire，遍历网格，将火源方位进行入队，更新火源方位 $f g [i] [j] = 1$ ，表明火势在榜首秒时最早出现在此处；
运用 BFS，模仿 $t$ 秒的火势延伸，火势在这 $t$ 秒内所延伸到的新方位，均看作为开始火源，即有 $f g [i] [j] = 1$ 。

若履行完 $t$ 秒后，火势已延伸到人员开始方位 $(0, 0)$ ，那么推迟 $t$ 秒动身不可行，直接回来 False；
创建用于模仿人员移动的行列 people，将开始方位 $(0, 0)$ 进行入队，更新 $p g [0] [0] = 1$ 。

运用 BFS，按照「先火后人」的方法，同步模仿「火势延伸」和「人员移动」进程。一般方位，只要火势延伸到，那么人将无法移动到此处；安全屋方位，需求判别是否与火势同一时刻抵达。

为了便利，将「火势延伸」和「人员移动」一致成 update 操作，入参包含当前行列 d，标识位 isFire，以及移动偏移量 offset。

在进行 $t$ 秒的火势延伸时，调用 $t$ 次的 update(fire, true, 0)。在火势和人员同步模仿时，别离调用 update(fire, true, 1) 和 update(people, false, 1)。

运用示例 $1$ 来举个：

Java 代码：

class Solution {
    int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    int n, m;
    boolean ok;
    int[][] g, fg, pg;
    public int maximumMinutes(int[][] grid) {
        g = grid;
        n = g.length; m = g[0].length;
        fg = new int[n][m]; pg = new int[n][m];
        if (!check(0)) return -1;
        int l = 0, r = n * m;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r == m * n ? (int)1e9 : r;
    }
    boolean check(int t) {
        ok = false;
        Deque<int[]> frie = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                fg[i][j] = pg[i][j] = 0;
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    frie.addLast(new int[]{i, j});
                }
            }
        }
        while(t-- > 0) update(frie, true, 0);  // 先履行 t 秒的火势延伸
        if (fg[0][0] != 0) return false;
        Deque<int[]> people = new ArrayDeque<>();
        pg[0][0] = 1;
        people.addLast(new int[]{0, 0});
        while (!people.isEmpty()) {
            // 先火后人, 同步进行
            update(frie, true, 1);
            update(people, false, 1);
            if (ok) return true;
        }
        return false;
    }
    void update(Deque<int[]> deque, boolean isFrie, int offset) {
        int sz = deque.size();
        while (sz-- > 0) {
            int[] info = deque.pollFirst();
            int x = info[0], y = info[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (isFrie) {
                    if (fg[nx][ny] != 0) continue;
                    fg[nx][ny] = fg[x][y] + offset;
                } else {
                    if (nx == n - 1 && ny == m - 1 && (fg[nx][ny] == 0 || fg[nx][ny] == pg[x][y] + offset)) ok = true;  // 火尚未抵达 或 一起抵达
                    if (fg[nx][ny] != 0 || pg[nx][ny] != 0) continue;
                    pg[nx][ny] = pg[x][y] + offset;
                }
                deque.addLast(new int[]{nx, ny});
            }
        }
    }
}

C++ 代码：

class Solution {
public:
    vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int n, m;
    bool ok;
    vector<vector<int>> g, fg, pg;
    int maximumMinutes(vector<vector<int>>& grid) {
        g = grid;
        n = g.size(); m = g[0].size();
        fg = vector<vector<int>>(n, vector<int>(m, 0)), pg = vector<vector<int>>(n, vector<int>(m, 0));
        if (!check(0)) return -1;
        int l = 0, r = n * m;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r == n * m ? (int)1e9 : r;
    }
    bool check(int t) {
        ok = false;
        deque<vector<int>> frie;   
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                fg[i][j] = pg[i][j] = 0;
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    frie.push_back({i, j});
                }
            }
        }
        while (t-- > 0) update(frie, true, 0);
        if (fg[0][0] != 0) return false;
        deque<vector<int>> people;
        pg[0][0] = 1;
        people.push_back({0, 0});
        while (!people.empty()) {
            update(frie, true, 1);
            update(people, false, 1);
            if (ok) return true;
        }
        return false;
    }
    void update(deque<vector<int>>& deque, bool isFrie, int offset) {
        int sz = deque.size();
        while (sz-- > 0) {
            vector<int> info = deque.front();
            deque.pop_front();
            int x = info[0], y = info[1];
            for (vector<int> dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (isFrie) {
                    if (fg[nx][ny] != 0) continue;                    
                    fg[nx][ny] = fg[x][y] + offset;
                } else {
                    if (nx == n - 1 && ny == m - 1 && (fg[nx][ny] == 0 || fg[nx][ny] == pg[x][y] + offset)) ok = true;
                    if (fg[nx][ny] != 0 || pg[nx][ny] != 0) continue;
                    pg[nx][ny] = pg[x][y] + offset;
                }
                deque.push_back({nx, ny});
            }
        }
    }
};

Python 代码：

from collections import deque
class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        ok = False
        g = grid
        n, m = len(g), len(g[0])
        fg, pg = [[0] * m for _ in range(n)], [[0] * m for _ in range(n)]
        def update(d, isFire, offset):
            nonlocal ok
            sz = len(d)
            for _ in range(sz):
                x, y = d.popleft()
                for di in dirs:
                    nx, ny = x + di[0], y + di[1]
                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue
                    if g[nx][ny] == 2:
                        continue
                    if isFire:
                        if fg[nx][ny] != 0:
                            continue
                        fg[nx][ny] = fg[x][y] + offset
                    else:
                        if nx == n - 1 and ny == m - 1 and (fg[nx][ny] == 0 or fg[nx][ny] == pg[x][y] + offset):
                            ok = True
                        if fg[nx][ny] != 0 or pg[nx][ny] != 0:
                            continue
                        pg[nx][ny] = pg[x][y] + offset
                    d.append((nx, ny))
        def check(t):
            nonlocal ok
            ok = False
            fire = deque()
            for i in range(n):
                for j in range(m):
                    fg[i][j] = pg[i][j] = 0
                    if g[i][j] == 1:
                        fg[i][j] = 1
                        fire.append((i, j))
            for _ in range(t):
                update(fire, True, 0)
            if fg[0][0] != 0:
                return False
            people = deque()
            pg[0][0] = 1
            people.append((0, 0))
            while people:
                update(fire, True, 1)
                update(people, False, 1)
                if ok:
                    return True
            return False
        if not check(0):
            return -1
        l, r = 0, n * m
        while l < r:
            mid = l + r + 1 >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return int(1e9) if r == n * m else r

TypeScript 代码：

function maximumMinutes(grid: number[][]): number {
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    const g = grid;
    const n = g.length, m = g[0].length;
    const fg = Array.from({length: n}, () => Array(m).fill(0)), pg = Array.from({length: n}, () => Array(m).fill(0));
    let ok = false;
    const update = function(d: number[][], isFire: boolean, offset: number) {
        let sz = d.length;
        while (sz-- > 0) {
            const info = d.shift();
            const x = info[0], y = info[1];
            for (let di of dirs) {
                const nx = x + di[0], ny = y + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (isFire) {
                    if (fg[nx][ny] != 0) continue;
                    fg[nx][ny] = fg[x][y] + offset;
                } else {
                    if (nx == n - 1 && ny == m - 1 && (fg[nx][ny] == 0 || fg[nx][ny] == pg[x][y] + offset)) ok = true;
                    if (fg[nx][ny] != 0 || pg[nx][ny] != 0) continue;
                    pg[nx][ny] = pg[x][y] + offset;
                }
                d.push([nx, ny]);
            }
        }
    }
    const check = function(t: number): boolean {
        ok = false
        const fire = new Array()
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                fg[i][j] = pg[i][j] = 0;
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    fire.push([i, j]);
                }
            }
        }
        while (t-- > 0) update(fire, true, 0);
        if (fg[0][0] != 0) return false;
        const people = new Array();
        pg[0][0] = 1;
        people.push([0, 0]);
        while (people.length != 0) {
            update(fire, true, 1);
            update(people, false, 1);
            if (ok) return true;
        }
        return false;
    }
    if (!check(0)) return -1;
    let l = 0, r = n * m;
    while (l < r) {
        const mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return r == n * m ? 1e9 : r;
};

时刻复杂度：在值域 $[0, n m]$ 范围内进行二分，二分 check 的 BFS 完成复杂度为 $O (n m)$ 。全体复杂度为 $O(nm log{nm})$
空间复杂度： $O (n m)$

BFS + 分类评论

经过上述解法，咱们发现存在很多重复计算：例如每次仅有确认的“火势延伸”进程，以及每次依据最新开始火势（由推迟动身时刻 $t$ 所决定）进行的“人员移动”进程，都是不必要的，可经过比较双方抵达时刻来求解。

详细的，仍是用 fg 和 pg，别离预处理出「火势」和「人员」抵达每个网格的最早时刻。其间火势延伸仅有确认，而人员的预处理是在不考虑火势的情况下进行。

依据 $f = f g [n - 1] [m - 1]$ 和 $p = p g [n - 1] [m - 1]$ 进行分情况评论：

若 $p = 0$ ：人与安全屋不连通，回来 $- 1$ ；
若 $f = 0$ ：火与安全屋不连通，一起上述条件不满足（ $p \neq = 0$ ），即人与安全屋是联通，回来 $1 e 9$ ；
若 $f < p$ ：火和人都能抵达安全屋。即使不考虑人员半途被火影响（人员或许无法按照最佳道路前往安全屋）的情况下，火也比人要更早抵达安全屋，回来 $- 1$ ；
若 $f ⩾ p$ ：抱负情况下，人比火更早抵达安全屋，但存在「人火一起抵达」、「人员半途被烧」或「通路被火拦截」等问题，需求进一步分情况评论：

不难发现，因为安全屋的坐落 $(n - 1, m - 1)$ ，人员只能从 $(n - 1, m - 2)$ 或 $(n - 2, m - 1)$ 两个方位之一抵达安全屋（这两个归于一般方位，不答应人和火一起抵达），因而能够将「对特殊方位安全屋」的评论转为「对一般方位」的评论：
- 若 $p g [n - 1] [m - 2] \neq = 0$ ，人与该方位联通，且 $f - p + p g [n - 1] [m - 2] < f g [n - 1] [m - 2]$ ，人比火更早抵达该方位，回来 $f - p$ ；
- 若 $p g [n - 2] [m - 1] \neq = 0$ ，人与该方位联通，且 $f - p + p g [n - 2] [m - 1] < f g [n - 2] [m - 1]$ ，人比火更早抵达该方位，回来 $f - p$ ；
- 否则，阐明推迟 $f - p$ 秒动身，唯二的通路会被火提前拦截，需求早一秒动身，回来 $f - p - 1$ ;

Java 代码：

class Solution {
    int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    int[][] g;
    int n, m;
    public int maximumMinutes(int[][] grid) {
        g = grid;
        n = g.length; m = g[0].length;
        int[][] fg = new int[n][m], pg = new int[n][m];
        Deque<int[]> fire = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    fire.addLast(new int[]{i, j});
                }
            }
        }
        bfs(fire, fg);
        Deque<int[]> people = new ArrayDeque<>();
        people.addLast(new int[]{0, 0});
        pg[0][0] = 1;
        bfs(people, pg);
        int p = pg[n - 1][m - 1], f = fg[n - 1][m - 1], ans = f - p;
        if (p == 0) return -1;
        if (f == 0) return (int)1e9;
        if (p > f) return -1;
        if (pg[n - 1][m - 2] != 0 && ans + pg[n - 1][m - 2] < fg[n - 1][m - 2]) return ans;
        if (pg[n - 2][m - 1] != 0 && ans + pg[n - 2][m - 1] < fg[n - 2][m - 1]) return ans;
        return ans - 1;
    }
    void bfs(Deque<int[]> d, int[][] time) {
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0], y = info[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (time[nx][ny] != 0) continue;
                time[nx][ny] = time[x][y] + 1;
                d.addLast(new int[]{nx, ny});
            }
        }
    }
}

C++ 代码：

class Solution {
public:
    vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    vector<vector<int>> g;
    int n, m;
    int maximumMinutes(vector<vector<int>>& grid) {
        g = grid;
        n = g.size(); m = g[0].size();
        vector<vector<int>> fg = vector<vector<int>>(n, vector<int>(m, 0)), pg = vector<vector<int>>(n, vector<int>(m, 0));
        deque<pair<int, int>> fire;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    fire.push_back({i, j});
                }
            }
        }
        bfs(fire, fg);
        deque<pair<int, int>> people;
        people.push_back({0, 0});
        pg[0][0] = 1;
        bfs(people, pg);
        int p = pg[n - 1][m - 1], f = fg[n - 1][m - 1], ans = f - p;
        if (p == 0) return -1;
        if (f == 0) return (int)1e9;
        if (p > f) return -1;
        if (pg[n - 1][m - 2] != 0 && ans + pg[n - 1][m - 2] < fg[n - 1][m - 2]) return ans;
        if (pg[n - 2][m - 1] != 0 && ans + pg[n - 2][m - 1] < fg[n - 2][m - 1]) return ans;
        return ans - 1;
    }
    void bfs(deque<pair<int, int>>& d, vector<vector<int>>& time) {
        while (!d.empty()) {
            pair<int, int> info = d.front();
            d.pop_front();
            int x = info.first, y = info.second;
            for (vector<int> dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (time[nx][ny] != 0) continue;
                time[nx][ny] = time[x][y] + 1;
                d.push_back({nx, ny});
            }
        }
    }
};

Python 代码：

from collections import deque
class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        g = grid
        n, m = len(g), len(g[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        def bfs(d, tn):
            while d:
                info = d.popleft()
                x, y = info[0], info[1]
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue
                    if g[nx][ny] == 2:
                        continue
                    if tn[nx][ny]:
                        continue
                    tn[nx][ny] = tn[x][y] + 1
                    d.append((nx, ny))
        fg, pg = [[0] * m for _ in range(n)], [[0] * m for _ in range(n)]
        fire = deque()
        for i in range(n):
            for j in range(m):
                if g[i][j] == 1:
                    fg[i][j] = 1
                    fire.append((i, j))
        bfs(fire, fg)
        people = deque()
        people.append((0, 0))
        pg[0][0] = 1
        bfs(people, pg)
        p, f = pg[-1][-1], fg[-1][-1]
        ans = f - p
        if p == 0:
            return -1
        if f == 0:
            return int(1e9)
        if p > f:
            return -1
        if pg[-1][-2] != 0 and ans + pg[-1][-2] < fg[-1][-2]:
            return ans
        if pg[-2][-1] != 0 and ans + pg[-2][-1] < fg[-2][-1]:
            return ans
        return ans - 1

TypeScript 代码：

function maximumMinutes(grid: number[][]): number {
    const g = grid;
    const n = g.length, m = g[0].length;
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const bfs = function (d: number[][], time: number[][]): void {
        while (d.length > 0) {
            const info = d.shift() as number[];
            const x = info[0], y = info[1];
            for (const dir of dirs) {
                const nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (g[nx][ny] == 2) continue;
                if (time[nx][ny] != 0) continue;
                time[nx][ny] = time[x][y] + 1;
                d.push([nx, ny]);
            }
        }
    }
    const fg = Array.from({ length: n }, () => Array(m).fill(0));
    const pg = Array.from({ length: n }, () => Array(m).fill(0));
    const fire = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (g[i][j] == 1) {
                fg[i][j] = 1;
                fire.push([i, j]);
            }
        }
    }
    bfs(fire, fg);
    const people = [];
    people.push([0, 0]);
    pg[0][0] = 1;
    bfs(people, pg);
    const p = pg[n - 1][m - 1], f = fg[n - 1][m - 1], ans = f - p;
    if (p == 0) return -1;
    if (f == 0) return 1e9;
    if (p > f) return -1;
    if (pg[n - 1][m - 2] != 0 && ans + pg[n - 1][m - 2] < fg[n - 1][m - 2]) return ans;
    if (pg[n - 2][m - 1] != 0 && ans + pg[n - 2][m - 1] < fg[n - 2][m - 1]) return ans;
    return ans - 1;
};

时刻复杂度： $O (n m)$
空间复杂度： $O (n m)$

最后

这是咱们「刷穿 LeetCode」系列文章的第 No.2258 篇，系列开端于 2021/01/01，截止于开始日 LeetCode 上共有 1916 道题目，部分是有锁题，咱们将先把一切不带锁的题目刷完。

在这个系列文章里边，除了解说解题思路以外，还会尽或许给出最为简练的代码。假如涉及通解还会相应的代码模板。

为了便利各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可拜访排版精巧的合集新基地

2258. 逃离火灾 : 详解如何从「二分」到「分类讨论」(图解过程)

题目描绘

二分 + BFS

BFS + 分类评论

最后

相关文章

SpringBoot技术实践-SpringRetry重试框架

结合tfsec与Terragrunt保护基础设施即代码

探索Table组件虚拟化

第一篇 介绍ReactiveX

作者信息

第一篇介绍ReactiveX