2258. Escape the Spreading Fire

HardBreadth-First SearchArrayBinary SearchMatrix

Problem Description

We are given a grid represented by a 2D array, where we start at the top-left corner and aim to reach the bottom-right corner, which is a safehouse. Each cell in the grid can be either grass (0), fire (1), or a wall (2). We can only move on grass cells, and every minute, the fire cells spread to all adjacent grass cells, but cannot pass through walls. The goal is to find out the longest time we can wait in the starting cell before beginning our journey to the safehouse, while still ensuring a safe arrival. If it's impossible to reach the safehouse, we return -1. However, if no amount of waiting prevents us from reaching the safehouse, we return a very large number, specifically 10^9. The problem involves understanding the dynamics of how the fire spreads and navigating through the grid to achieve our goal.

Flowchart Walkthrough

To analyze Leetcode problem 2258, "Escape the Spreading Fire", let's utilize the algorithm Flowchart. We can conduct a thorough breakdown:

Is it a graph?
- Yes: The problem can be seen as a graph where each cell in the grid is a node, and each adjacent pair of cells shares an edge.
Is it a tree?
- No: The grid can contain cycles; it's neither rooted nor acyclic like a tree. For instance, you can move around blocks on the grid that can lead you back to a start point.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The grid is not explicitly directed and can potentially contain cycles, thereby negating the properties of a DAG.
Is the problem related to shortest paths?
- Yes: The objective is to find an escape route; thus, finding the shortest possible safe path to the boundary of the grid is crucial to escaping the fire.
Is the graph weighted?
- No: Typically, in a grid problem such as this, each move from one cell to an adjacent one is considered to have uniform cost unless specified differently.
Conclusion: According to the flowchart and the characteristics of the problem, using Breadth-First Search (BFS) is the appropriate choice for this type of unweighted, shortest path problem on the grid.

Using BFS for this problem is especially fitting due to:

Its ability to explore all potential paths simultaneously in layers, ensuring that the shortest path is explored first.
The need to process neighbors uniformly, which aligns well with the BFS's nature of exploring all nodes at the present depth before moving deeper.

These characteristics make BFS not only suitable but efficient for handling and solving the "Escape the Spreading Fire" problem regarding pathway feasibility and optimal escape routes.

Intuition

The solution to this problem involves two main ideas: binary search and breadth-first search (BFS).

Firstly, we notice that if it's possible to wait $t$ minutes and still reach the safehouse, then any number of minutes less than $t$ would also work. This monotonic property is perfect for applying binary search, allowing us to efficiently narrow down the maximum number of minutes we can wait.

The binary search operates between a range from $-1$ to $m \times n$ , where $m$ and $n$ are the dimensions of the grid. Each iteration checks the midpoint of this range to see if it's possible to safely wait that long at the start and then reach the safehouse. If midpoint $mid$ works, the logic dictates that we might be able to wait even longer, so we shift our search to the range above $mid$ . Conversely, if $mid$ doesn't work, we need to try fewer minutes, so our search focuses below $mid$ .

The second idea is using BFS to simulate the scenario at each $mid$ value chosen by our binary search. This involves simulating the fire spread after waiting at the start for $mid$ minutes and then proceeding with our traversal across the grid, checking at each step if the fire has reached our location or if there's a path available to the safehouse. If the path is clear, we confirm that waiting $mid$ minutes is feasible. BFS is well-suited for this scenario because it explores all possible moves in a level-wise manner, paralleling the minute-by-minute spread of the fire we need to consider.

By combining binary search and BFS, we can efficiently arrive at the maximum amount of time we can stay put at the beginning before making our way to the safehouse, ensuring our safety given the dynamic constraint of the spreading fire.

Learn more about Breadth-First Search and Binary Search patterns.

Solution Approach

The implementation of the solution involves both binary search and breadth-first search (BFS) algorithms to traverse the 2D grid efficiently under constraints defined by the fire spread. Here's a breakdown of the approaches used:

1. Binary Search Algorithm: To optimize the search for the maximum number of minutes we can stay put, binary search halves the search space in each iteration. We use two pointers, l and r, to denote the range within which we perform the binary search. We begin with l=-1 (representing not waiting at all but immediately moving) and r=m*n (representing an unreasonably large waiting time, greater than the number of cells in the grid, ensuring the safehouse will always be burnt down before we begin our move). Eventually, our binary search will home in on the maximum safe wait time, if it exists.

2. Breadth-First Search (BFS): The check function is where BFS comes into play. It simulates the fire spread and checks whether we can reach the safehouse safely if we wait t minutes before moving. It involves two BFS loops:

Fire Spread Simulation: Before starting our move, we simulate the spread of fire for t minutes using BFS. We enqueue all initial fire cells and then, for each minute, dequeue these cells, then enqueue all their adjacent grass cells, causing them to catch fire. We perform this until the waited minutes t are used up or there are no more fire cells to spread.
Path Finding to the Safehouse: After simulating the fire spread for t minutes, we start our journey from the top-left cell towards the safehouse with another BFS. We continue spreading the fire after each move to simulate its natural spread. During our traversal, we skip cells that are already on fire or walls and mark the cells we pass through to avoid revisiting them. If we reach the safehouse (bottom-right cell), then waiting for t minutes is feasible.

The solution iteratively uses the check function within the binary search to pinpoint the exact t value that represents the longest time we can wait without jeopardizing our chance to safely arrive at the safehouse.

Data Structures Used:

A deque is used to maintain the BFS frontier, allowing efficient pop and append operations representing cells to visit next.
A 2D list fire to keeps track of which cells are on fire at any given minute.

Edge Cases Handling:

If the safehouse immediately catches fire after reaching it, it still counts as safe arrival.
If we can indefinitely wait because the safehouse will never catch fire or we can reach it regardless of waiting time, we return 10^9.

Through this approach, the problem which originally looks like a complex simulation is handled methodically through a combination of well-established algorithms, ensuring an efficient and systematic solution that satisfies the given constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example of a small grid. Imagine the following 3x3 grid where 0 represents grass, 1 represents fire, and 2 is a wall:

Grid:
0 1 0
0 0 2
2 0 0

The top-left corner [0][0] is our starting point, and the bottom-right corner [2][2] is the safehouse.

Step 1: Initial Binary Search Setup

Set l to -1, because we have not waited at all, and r to 3*3 which is 9, an unreasonably high wait time guaranteeing the safehouse will be burnt down if we wait that long.

Step 2: Perform Binary Search

The binary search begins with the midpoint mid = (l + r) / 2 which is 4. Now we need to check if waiting for 4 minutes is feasible.

Step 3: BFS Simulation of Fire Spread for mid Minutes

Using BFS, we start the fire spread simulation from the fire cell [0][1]. After 1 minute, the grid would look like this if we were there to spread the fire:

After 1 minute:
0 1 1
0 1 2
2 0 0

We continue this simulation up to 4 minutes (our mid value). However, after 2 minutes, the fire would have already spread to the safehouse cell [2][2], rendering further simulation unnecessary as we've proven that waiting for 4 minutes is not feasible. The check function would return false.

Step 4: Update Binary Search Range

Since waiting 4 minutes is too long, we adjust the binary search range: r becomes mid - 1, which is 3.
We find the new mid of this updated range, being 1. Again, the check function performs the same simulation, and it turns out that we’re safe if we start moving after 1 minute:

After 1 minute:
0 1 1
0 0 2
2 0 0

This means we can start at the cell [0][0] and reach the safehouse moving downwards then right without ever coming into a cell that will catch fire the next minute.

Step 5: Repeat Binary Search and BFS Until Convergence

The binary search continues, with l being updated to mid when waiting is successful, or r being updated to mid - 1 when not successful. Eventually, we converge to the longest time we can wait.
In this case, with further iteration, we would find that we could wait 1 minute, and 2 minutes is too long because the fire would spread to [1][2] on its second move, and [2][2] (the safehouse) will be next. Therefore, the maximum time we can wait is 1 minute.

Final Outcome

Our function would return 1 as the longest time we could wait at the starting cell [0][0] before moving towards the safehouse and arriving safely, without getting caught by the fire.

Solution Implementation

1from collections import deque
2from itertools import pairwise
3
4class Solution:
5    def maximum_minutes(self, grid: List[List[int]]) -> int:
6      
7        # Helper function to spread fire by one step
8        def spread_fire(fire_queue: deque) -> deque:
9            new_fire_queue = deque()
10            while fire_queue:
11                row, col = fire_queue.popleft()
12                for delta_row, delta_col in pairwise(fire_directions):
13                    x, y = row + delta_row, col + delta_col
14                    if 0 <= x < rows and 0 <= y < cols and not is_on_fire[x][y] and grid[x][y] == 0:
15                        is_on_fire[x][y] = True
16                        new_fire_queue.append((x, y))
17            return new_fire_queue
18
19        # Helper function to check if it's possible to escape with a given head start
20        def can_escape_with_head_start(head_start: int) -> bool:
21            # Reset the fire spread simulation
22            for i in range(rows):
23                for j in range(cols):
24                    is_on_fire[i][j] = False
25          
26            fire_queue = deque()
27            for i, row in enumerate(grid):
28                for j, cell in enumerate(row):
29                    if cell == 1:
30                        is_on_fire[i][j] = True
31                        fire_queue.append((i, j))
32
33            # Let the fire spread for 'head_start' steps
34            while head_start and fire_queue:
35                fire_queue = spread_fire(fire_queue)
36                head_start -= 1
37          
38            # If the starting cell is on fire, not possible to escape
39            if is_on_fire[0][0]:
40                return False
41
42            # Queue for BFS to check for an escape path
43            escape_queue = deque([(0, 0)])
44            visited = [[False] * cols for _ in range(rows)]
45            visited[0][0] = True
46          
47            while escape_queue:
48                for _ in range(len(escape_queue)):
49                    row, col = escape_queue.popleft()
50                    if is_on_fire[row][col]:
51                        continue
52                    for delta_row, delta_col in pairwise(fire_directions):
53                        x, y = row + delta_row, col + delta_col
54                        if (
55                            0 <= x < rows
56                            and 0 <= y < cols
57                            and not visited[x][y]
58                            and not is_on_fire[x][y]
59                            and grid[x][y] == 0
60                        ):
61                            if x == rows - 1 and y == cols - 1:
62                                return True
63                            visited[x][y] = True
64                            escape_queue.append((x, y))
65                # Spread fire after each step of player movement
66                fire_queue = spread_fire(fire_queue)
67            return False
68
69        # Initialize parameters
70        rows, cols = len(grid), len(grid[0])
71        fire_directions = (-1, 0, 1, 0, -1)  # Directions for fire to spread
72        is_on_fire = [[False] * cols for _ in range(rows)]
73      
74        # Binary search for the maximum minutes
75        left, right = -1, rows * cols
76        while left < right:
77            mid = (left + right + 1) // 2
78            if can_escape_with_head_start(mid):
79                left = mid
80            else:
81                right = mid - 1
82      
83        # Return the maximum minutes if the player can escape, else return large number
84        return int(1e9) if left == rows * cols else left
85

1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.Deque;
4
5class Solution {
6    private int[][] grid;
7    private boolean[][] onFire;
8    private boolean[][] visited;
9    private final int[] directions = {-1, 0, 1, 0, -1}; // Represents the directions for movement (up, right, down, left)
10    private int rows;
11    private int columns;
12
13    // Calculate the maximum number of minutes you can stay in the house before you have to escape.
14    public int maximumMinutes(int[][] grid) {
15        rows = grid.length;
16        columns = grid[0].length;
17        this.grid = grid;
18        onFire = new boolean[rows][columns];
19        visited = new boolean[rows][columns];
20        int left = -1, right = rows * columns;
21      
22        // Binary search to find the maximum minutes.
23        while (left < right) {
24            int mid = (left + right + 1) >> 1;
25            if (canEscape(mid)) {
26                left = mid;
27            } else {
28                right = mid - 1;
29            }
30        }
31      
32        // If maximum minutes is equal to rows * columns, return a large number implying infinite time to escape
33        return left == rows * columns ? 1000000000 : left;
34    }
35
36    // Check if it's possible to escape given the time head start.
37    private boolean canEscape(int timeHeadStart) {
38        // Reset the on fire and visited grid for each check
39        for (int i = 0; i < rows; ++i) {
40            Arrays.fill(onFire[i], false);
41            Arrays.fill(visited[i], false);
42        }
43      
44        Deque<int[]> fireQueue = new ArrayDeque<>();
45        // Initialize the fire queue with the initial fire positions
46        for (int i = 0; i < rows; ++i) {
47            for (int j = 0; j < columns; ++j) {
48                if (grid[i][j] == 1) {
49                    fireQueue.offer(new int[] {i, j});
50                    onFire[i][j] = true;
51                }
52            }
53        }
54      
55        // Spread fire for 'timeHeadStart' minutes
56        for (; timeHeadStart > 0 && !fireQueue.isEmpty(); --timeHeadStart) {
57            fireQueue = spreadFire(fireQueue);
58        }
59      
60        // If starting position is on fire, escape is impossible
61        if (onFire[0][0]) {
62            return false;
63        }
64      
65        Deque<int[]> personQueue = new ArrayDeque<>();
66        personQueue.offer(new int[] {0, 0});
67        visited[0][0] = true;
68      
69        // The loop for moving the player
70        while (!personQueue.isEmpty()) {
71            fireQueue = spreadFire(fireQueue); // Spread fire each minute
72            for (int d = personQueue.size(); d > 0; --d) {
73                int[] position = personQueue.poll();
74                if (onFire[position[0]][position[1]]) {
75                    continue; // Skip if the current position is on fire
76                }
77                // Explore adjacent squares
78                for (int k = 0; k < 4; ++k) {
79                    int newX = position[0] + directions[k], newY = position[1] + directions[k + 1];
80                    // Check if the new position is within bounds and is not on fire or visited
81                    if (newX >= 0 && newX < rows && newY >= 0 && newY < columns && !onFire[newX][newY] && !visited[newX][newY]
82                        && grid[newX][newY] == 0) {
83                        // If reached the bottom-right corner, escape is possible
84                        if (newX == rows - 1 && newY == columns - 1) {
85                            return true;
86                        }
87                        visited[newX][newY] = true;
88                        personQueue.offer(new int[] {newX, newY});
89                    }
90                }
91            }
92        }
93        return false;
94    }
95
96    // Helper function to spread fire in the grid.
97    private Deque<int[]> spreadFire(Deque<int[]> fireQueue) {
98        Deque<int[]> nextFireQueue = new ArrayDeque<>();
99        while (!fireQueue.isEmpty()) {
100            int[] currentFirePos = fireQueue.poll();
101            // Spread fire to the adjacent squares
102            for (int k = 0; k < 4; ++k) {
103                int newX = currentFirePos[0] + directions[k], newY = currentFirePos[1] + directions[k + 1];
104                // Ignite the new square if it's within the grid, not already on fire, and not a wall
105                if (newX >= 0 && newX < rows && newY >= 0 && newY < columns && !onFire[newX][newY] && grid[newX][newY] == 0) {
106                    onFire[newX][newY] = true;
107                    nextFireQueue.offer(new int[] {newX, newY});
108                }
109            }
110        }
111        return nextFireQueue;
112    }
113}
114

1#include <vector>
2#include <queue>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    int maximumMinutes(vector<vector<int>>& grid) {
9        int rows = grid.size(), cols = grid[0].size(); // dimensions of the grid
10        bool visited[rows][cols]; // visited cells by the player
11        bool fireSpread[rows][cols]; // cells reached by the fire
12        int directions[5] = {-1, 0, 1, 0, -1}; // used to iterate over the four adjacent cells
13
14        // Lambda function to spread the fire for one unit of time
15        auto spreadFire = [&](queue<pair<int, int>>& fireQueue) {
16            queue<pair<int, int>> newFireQueue;
17            while (!fireQueue.empty()) {
18                auto [i, j] = fireQueue.front();
19                fireQueue.pop();
20                for (int k = 0; k < 4; ++k) {
21                    int newX = i + directions[k], newY = j + directions[k + 1];
22                    if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !fireSpread[newX][newY] && grid[newX][newY] == 0) {
23                        fireSpread[newX][newY] = true;
24                        newFireQueue.emplace(newX, newY);
25                    }
26                }
27            }
28            return newFireQueue;
29        };
30
31        // Lambda function to check if the player can escape when starting after 't' minutes
32        auto canEscape = [&](int t) {
33            memset(visited, false, sizeof(visited));
34            memset(fireSpread, false, sizeof(fireSpread));
35            queue<pair<int, int>> fireQueue;
36
37            // Initialize fire spread
38            for (int i = 0; i < rows; ++i) {
39                for (int j = 0; j < cols; ++j) {
40                    if (grid[i][j] == 1) {
41                        fireQueue.emplace(i, j);
42                        fireSpread[i][j] = true;
43                    }
44                }
45            }
46
47            // Spread fire by 't' minutes
48            while (t-- > 0 && !fireQueue.empty()) {
49                fireQueue = spreadFire(fireQueue);
50            }
51
52            // If fire is already at the starting cell, return false
53            if (fireSpread[0][0]) {
54                return false;
55            }
56
57            // Try to escape the building
58            queue<pair<int, int>> playerQueue;
59            playerQueue.emplace(0, 0);
60            visited[0][0] = true;
61
62            while (!playerQueue.empty()) {
63                // Spread fire each minute
64                fireQueue = spreadFire(fireQueue);
65
66                for (int size = playerQueue.size(); size > 0; --size) {
67                    auto [i, j] = playerQueue.front();
68                    playerQueue.pop();
69                  
70                    // Skip if current cell is on fire
71                    if (fireSpread[i][j]) {
72                        continue;
73                    }
74                  
75                    for (int k = 0; k < 4; ++k) {
76                        int newX = i + directions[k], newY = j + directions[k + 1];
77                        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited[newX][newY] && !fireSpread[newX][newY] && grid[newX][newY] == 0) {
78                            if (newX == rows - 1 && newY == cols - 1) {
79                                // Reached bottom-right corner, return true
80                                return true;
81                            }
82                            visited[newX][newY] = true;
83                            playerQueue.emplace(newX, newY);
84                        }
85                    }
86                }
87            }
88            return false;
89        };
90
91        // Binary search to find the maximum minutes the player can wait before starting to escape
92        int left = -1, right = rows * cols;
93        while (left < right) {
94            int mid = (left + right + 1) >> 1; // Midpoint for binary search
95            if (canEscape(mid)) {
96                left = mid; // If the player can escape after 'mid' minutes, search in the higher half
97            } else {
98                right = mid - 1; // Else, search in the lower half
99            }
100        }
101        // If the player can always escape without the fire, return 1e9; otherwise return the maximum minutes
102        return left == rows * cols ? 1000000000 : left;
103    }
104};
105

1// Specifies the direction vectors for up, right, down, and left movements on the grid.
2const directions: number[] = [-1, 0, 1, 0, -1];
3
4// Spreads the fire one step in all possible directions and returns the new queue of fire positions.
5function spreadFire(queue: number[][], fireMatrix: boolean[][], grid: number[][], m: number, n: number): number[][] {
6    const newQueue: number[][] = [];
7    while (queue.length) {
8        const [row, col] = queue.shift()!;
9      
10        for (let k = 0; k < 4; ++k) {
11            const newRow = row + directions[k];
12            const newCol = col + directions[k + 1];
13          
14            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !fireMatrix[newRow][newCol] && grid[newRow][newCol] === 0) {
15                fireMatrix[newRow][newCol] = true;
16                newQueue.push([newRow, newCol]);
17            }
18        }
19    }
20    return newQueue;
21}
22
23// Checks if it is possible to escape before the given time "t" runs out.
24function canEscape(grid: number[][], fireMatrix: boolean[][], visited: boolean[][], timeLimit: number, m: number, n: number): boolean {
25    // Resets fireMatrix and visited for the current check.
26    for (let i = 0; i < m; ++i) {
27        fireMatrix[i].fill(false);
28        visited[i].fill(false);
29    }
30  
31    // Initializes the queue with the positions of the fire.
32    let fireQueue: number[][] = [];
33    for (let i = 0; i < m; ++i) {
34        for (let j = 0; j < n; ++j) {
35            if (grid[i][j] === 1) {
36                fireQueue.push([i, j]);
37                fireMatrix[i][j] = true;
38            }
39        }
40    }
41  
42    // Spreads fire up to the current timeLimit.
43    for (; timeLimit > 0 && fireQueue.length; --timeLimit) {
44        fireQueue = spreadFire(fireQueue, fireMatrix, grid, m, n);
45    }
46  
47    // If the starting point is already on fire, escape is impossible.
48    if (fireMatrix[0][0]) {
49        return false;
50    }
51  
52    // Begins BFS for the player starting at the top-left corner.
53    const escapeQueue: number[][] = [[0, 0]];
54    visited[0][0] = true;
55    while (escapeQueue.length) {
56        // Spread fire for each player's move.
57        fireQueue = spreadFire(fireQueue, fireMatrix, grid, m, n);
58      
59        for (let queueSize = escapeQueue.length; queueSize > 0; --queueSize) {
60            const [row, col] = escapeQueue.shift()!;
61          
62            // Skip if the current position is on fire.
63            if (fireMatrix[row][col]) {
64                continue;
65            }
66          
67            // Check all possible move directions.
68            for (let k = 0; k < 4; ++k) {
69                const newRow = row + directions[k];
70                const newCol = col + directions[k + 1];
71              
72                // Check if it is a valid move and not visited or on fire.
73                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol] && !fireMatrix[newRow][newCol] && grid[newRow][newCol] === 0) {
74                    // If the bottom-right corner is reached, the escape is possible.
75                    if (newRow === m - 1 && newCol === n - 1) {
76                        return true;
77                    }
78                    visited[newRow][newCol] = true;
79                    escapeQueue.push([newRow, newCol]);
80                }
81            }
82        }
83    }
84    return false;
85}
86
87// Calculates the maximum number of minutes the player has to escape before being caught by fire.
88function maximumMinutes(grid: number[][]): number {
89    const m = grid.length;
90    const n = grid[0].length;
91  
92    // These matrices keep track of areas set on fire and visited by the player.
93    const fireMatrix = Array.from({ length: m }, () => Array.from({ length: n }, () => false));
94    const visited = Array.from({ length: m }, () => Array.from({ length: n }, () => false));
95  
96    // Binary search variables for finding the maximum time.
97    let left = -1;
98    let right = m * n;
99  
100    // Binary search to find the maximum number of minutes for escape.
101    while (left < right) {
102        const mid = (left + right + 1) >> 1;
103      
104        // Check whether the player can escape if they wait for 'mid' minutes before starting to move.
105        if (canEscape(grid, fireMatrix, visited, mid, m, n)) {
106            left = mid;
107        } else {
108            right = mid - 1;
109        }
110    }
111  
112    // If the left pointer reaches the maximum, return an arbitrarily large number.
113    return left === m * n ? 1e9 : left;
114}
115

Time and Space Complexity

The time complexity of the provided code is O(m * n * log(m * n)). This complexity arises from the binary search which takes log(m * n) iterations, within each iteration a BFS (Breadth-First Search) is performed twice; once to spread the fire (spread) and once to check if it's possible to escape at time t (check). The BFS operations have a complexity of O(m * n) because, in the worst case, they might visit all cells in the grid. Therefore, when combined with binary search, the complexity is O(m * n * log(m * n)).

The space complexity is O(m * n) because of the fire and vis matrices which are used to record whether a cell has been burnt by the fire or visited by the person, respectively. Both of these matrices have dimensions equal to the grid, hence the O(m * n) space complexity. Additional space is consumed by queues used in BFS which in the worst case can hold all cells, not increasing the overall space complexity beyond O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls