逃离火灾

题目

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

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

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

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

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
class Solution {
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    bool check(vector<vector<int>> &grid, int t) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> on_fire(m, vector<int>(n));
        vector<pair<int, int>> f;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    on_fire[i][j] = true; 
                    f.emplace_back(i, j);
                }
            }
        }
        // 火的 BFS
        auto spread_fire = [&]() {
            vector<pair<int, int>> nf;
            for (auto &[i, j]: f) {
                for (auto &[dx, dy]: dirs) { 
                    int x = i + dx, y = j + dy;
                    if (0 <= x && x < m && 0 <= y && y < n && !on_fire[x][y] && grid[x][y] == 0) {
                        on_fire[x][y] = true; 
                        nf.emplace_back(x, y);
                    }
                }
            }
            f = move(nf);
        };
        while (t-- && !f.empty()) { 
            spread_fire(); 
        }
        if (on_fire[0][0]) {
            return false; 
        }

        vector<vector<int>> vis(m, vector<int>(n));
        vis[0][0] = true;
        vector<pair<int, int>> q{{0, 0}};
        while (!q.empty()) {
            vector<pair<int, int>> nq;
            for (auto &[i, j]: q) {
                if (on_fire[i][j]) continue;
                for (auto &[dx, dy]: dirs) {
                    int x = i + dx, y = j + dy;
                    if (0 <= x && x < m && 0 <= y && y < n && !on_fire[x][y] && !vis[x][y] && grid[x][y] == 0) {
                        if (x == m - 1 && y == n - 1) {
                            return true; 
                        }
                        vis[x][y] = true; 
                        nq.emplace_back(x, y);
                    }
                }
            }
            q = move(nq);
            spread_fire(); 
        }
        return false; 
    }

public:
    int maximumMinutes(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int left = -1, right = m * n + 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            (check(grid, mid) ? left : right) = mid;
        }
        return left < m * n ? left : 1'000'000'000;
    }
};