LeetCode_多源 BFS_中等_2258.逃离火灾

野性酷女 2024-02-19 10:58 52阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

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

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。如果两个格子有共同边，那么它们为相邻格子。

示例 1：  
![在这里插入图片描述][bb3c0f09b0e445e694eb777ca2d90d01.png]  
输入：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：**  
![在这里插入图片描述][92dbe3c8b7644085b1c965655c2b8cf7.png]

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

**示例 3：**  
![在这里插入图片描述][cb010053c9b3459e809fb38688bde204.png]  
输入：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

## 2.思路 ##

（1）BFS & 二分搜索  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_多源 BFS\_中等\_994.腐烂的橘子][LeetCode_ BFS_994.]

## 3.代码实现（Java） ##

//思路1————BFS & 二分搜索
    class Solution {
        
    
        final int INF = 1000000000;
        int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
        int m;
        int n;
    
        public int maximumMinutes(int[][] grid) {
        
            m = grid.length;
            n = grid[0].length;
            //保存每个格子着火的时间
            int[][] fireTime = new int[m][n];
            for (int i = 0; i < m; i++) {
        
                Arrays.fill(fireTime[i], INF);
            }
            bfs(grid, fireTime);
            //使用二分搜索查找在初始位置可以停留的最多分钟数
            int res = -1;
            int left = 0;
            int right = m * n;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (check(fireTime, grid, mid)) {
        
                    left = mid + 1;
                    res = mid;
                } else {
        
                    right = mid - 1;
                }
            }
            return res >= m * n ? INF : res;
        }
    
        //判断起点停留的时间为 stayTime 时，能否到达安全屋
        private boolean check(int[][] fireTime, int[][] grid, int stayTime) {
        
            boolean[][] visited = new boolean[m][n];
            Queue<int[]> queue = new ArrayDeque<>();
            queue.offer(new int[]{
        0, 0, stayTime});
            visited[0][0] = true;
            while (!queue.isEmpty()) {
        
                int[] index = queue.poll();
                int ci = index[0];
                int cj = index[1];
                int time = index[2];
                for (int[] dir : dirs) {
        
                    int ni = ci + dir[0];
                    int nj = cj + dir[1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
        
                        if (visited[ni][nj] || grid[ni][nj] == 2) {
        
                            continue;
                        }
                        //到达安全屋
                        if (ni == m - 1 && nj == n - 1) {
        
                            return fireTime[ni][nj] >= time + 1;
                        }
                        //火未到达当前位置
                        if (fireTime[ni][nj] > time + 1) {
        
                            queue.offer(new int[]{
        ni, nj, time + 1});
                            visited[ni][nj] = true;
                        }
                    }
                }
            }
            return false;
        }
    
        //多源 bfs
        public void bfs(int[][] grid, int[][] fireTime) {
        
            Queue<int[]> queue = new ArrayDeque<>();
            //将目前着火的格子坐标放入到队列中
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (grid[i][j] == 1) {
        
                        queue.offer(new int[]{
        i, j});
                        fireTime[i][j] = 0;
                    }
                }
            }
            int time = 1;
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    int[] index = queue.poll();
                    int ci = index[0];
                    int cj = index[1];
                    for (int[] dir : dirs) {
        
                        int ni = ci + dir[0];
                        int nj = cj + dir[1];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
        
                            if (grid[ni][nj] == 2 || fireTime[ni][nj] != INF) {
        
                                continue;
                            }
                            queue.offer(new int[]{
        ni, nj});
                            fireTime[ni][nj] = time;
                        }
                    }
                }
                time++;
            }
        }
    }

[bb3c0f09b0e445e694eb777ca2d90d01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/99b03e0c28e741d19c7a56f34d5f2376.png
[92dbe3c8b7644085b1c965655c2b8cf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/e9d3ecf80eb94613a199ee29b076ec6d.png
[cb010053c9b3459e809fb38688bde204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/c4109843716e41f2888d35e35f6fc86c.png
[Link 1]: https://leetcode.cn/problems/escape-the-spreading-fire/description/?envType=daily-question
[LeetCode_ BFS_994.]: https://xgqngu.blog.csdn.net/article/details/130698727