2258. 逃离火灾 (opens new window)

1.二分+BFS

二分条件：等待时间小于最佳等待时间，都可以成功逃离火灾；大于最佳等待时间则不能逃离。存在单调性因此可以使用二分找出最佳时间。

解题流程分为以下几步：

1. 使用BFS，计算出每个地方火势蔓延的时刻。
2. 二分法枚举等待时间，即初始化在(0,0)点的出发时刻，如果在某个点的当前时刻大于火势蔓延时刻，则认为这个点不可达，并使用BFS来寻找终点路径。

寻找迷宫路径采用DFS还是BFS?

无论是哪种算法，都需要开辟一个visit数组来记录已访问节点。

🚀DFS：适用于找出所有可能的不同的路径，同时算法实现上需要回溯+递归。

🚀BFS：适用于找出最短距离的路径，以及存在性判断。

class Solution {
    int[][] dir=new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    public int maximumMinutes(int[][] grid) {
        Deque<int[]> queue=new LinkedList<>();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1)queue.offerLast(new int[]{i,j});
                if(grid[i][j]==2) grid[i][j]=-1;
            }
        }
        //计算火焰蔓延
        while(queue.size()!=0){
            int[] tmp=queue.pollFirst();
            int x=tmp[0],y=tmp[1];
            int time=grid[x][y];
            for(int i=0;i<4;i++){
                int nextX=x+dir[i][0];
                int nextY=y+dir[i][1];
                if((nextX>=0&&nextX<grid.length)&&(nextY>=0&&nextY<grid[0].length)&&grid[nextX][nextY]==0){
                    grid[nextX][nextY]=time+1;
                    queue.offerLast(new int[]{nextX,nextY});
                }
            }
        }
        //二分逼近等待时间
        int left = 0, right = grid.length * grid[0].length + 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (bfs(grid, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if(left==grid.length*grid[0].length+1) return 1000000000;
        else{
            if(bfs(grid,right)) return right;
            return right - 1;
        }

    }
    public boolean bfs(int[][] grid, int nowTIme) {
        int[][] visit = new int[grid.length][grid[0].length];
        Deque<int[]> queue = new LinkedList<>();
        queue.offerLast(new int[]{0, 0, nowTIme});
        while (!queue.isEmpty()) {
            if(visit[grid.length-1][grid[0].length-1] ==1) return true;
            int[] nums = queue.pollFirst();
            int time = nums[2]+1;
            for (int i = 0; i < 4; i++) {
                int row = nums[0] + dir[i][0];
                int line = nums[1] + dir[i][1];
                if ((row >= 0 && row < grid.length) && (line >= 0 && line < grid[0].length) && grid[row][line] != -1&&visit[row][line]==0) {
                    if (grid[row][line]==0||time < grid[row][line] - 1) {
                        visit[row][line] = 1;
                        queue.offerLast(new int[]{row, line, time});
                    } else if (row == grid.length - 1 && line == grid[0].length - 1 && time <= grid[row][line] - 1) {
                        visit[row][line] = 1;
                        queue.offerLast(new int[]{row, line, time});
                    }
                }
            }
        }
        return false;
    }
}