{x}
blog image

Escape the Spreading Fire

You are given a 0-indexed 2D integer array grid of size m x n which represents a field. Each cell has one of three values:

  • 0 represents grass,
  • 1 represents fire,
  • 2 represents a wall that you and fire cannot pass through.

You are situated in the top-left cell, (0, 0), and you want to travel to the safehouse at the bottom-right cell, (m - 1, n - 1). Every minute, you may move to an adjacent grass cell. After your move, every fire cell will spread to all adjacent cells that are not walls.

Return the maximum number of minutes that you can stay in your initial position before moving while still safely reaching the safehouse. If this is impossible, return -1. If you can always reach the safehouse regardless of the minutes stayed, return 109.

Note that even if the fire spreads to the safehouse immediately after you have reached it, it will be counted as safely reaching the safehouse.

A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

 

Example 1:

Input: 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]]
Output: 3
Explanation: The figure above shows the scenario where you stay in the initial position for 3 minutes.
You will still be able to safely reach the safehouse.
Staying for more than 3 minutes will not allow you to safely reach the safehouse.

Example 2:

Input: grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
Output: -1
Explanation: The figure above shows the scenario where you immediately move towards the safehouse.
Fire will spread to any cell you move towards and it is impossible to safely reach the safehouse.
Thus, -1 is returned.

Example 3:

Input: grid = [[0,0,0],[2,2,0],[1,2,0]]
Output: 1000000000
Explanation: The figure above shows the initial grid.
Notice that the fire is contained by walls and you will always be able to safely reach the safehouse.
Thus, 109 is returned.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 300
  • 4 <= m * n <= 2 * 104
  • grid[i][j] is either 0, 1, or 2.
  • grid[0][0] == grid[m - 1][n - 1] == 0

Solution Explanation for Escape the Spreading Fire

This problem involves finding the maximum number of minutes you can wait at the starting point before moving to the safehouse, while still ensuring a safe path exists. The solution uses a combination of Binary Search and Breadth-First Search (BFS).

1. Binary Search:

The core idea is that if a waiting time t allows a safe escape, then any waiting time less than t will also allow a safe escape. This monotonicity makes binary search an efficient approach to find the maximum safe waiting time.

  • Search Space: The binary search iterates through the range of possible waiting times. The lower bound is -1 (representing immediate movement), and the upper bound is m * n (the maximum possible time before the fire fills the entire grid, where m and n are grid dimensions).

  • Check Function: The check(t) function is crucial. It determines if a given waiting time t allows a safe escape. This function uses BFS twice:

2. Breadth-First Search (BFS):

  • Fire Spread Simulation: The first BFS simulates the fire's spread over t minutes. It starts by identifying all initial fire cells. In each time step, it adds adjacent grass cells to the fire and updates the fire grid (a boolean matrix tracking fire locations). This ensures that we have an accurate representation of the fire spread before the person starts moving.

  • Escape Path Search: After simulating the fire spread for t minutes, the second BFS searches for a safe path from the starting point (0, 0) to the safehouse (m-1, n-1). This BFS only explores cells not yet on fire. If it reaches the safehouse, the person can safely escape with waiting time t.

3. Algorithm:

  1. Initialize: Set the binary search bounds l = -1 and r = m * n.
  2. Binary Search Loop: While l < r:
    • Calculate the middle waiting time mid = (l + r + 1) / 2.
    • Call check(mid):
      • Simulate fire spread for mid minutes.
      • Check if a safe path exists.
    • If check(mid) returns true (safe escape is possible), update l = mid. Otherwise, update r = mid - 1.
  3. Return Result: After the binary search, l holds the maximum safe waiting time. If l equals the upper bound m * n, it means an escape is always possible, so return 109. Otherwise, return l.

Time Complexity: O(m * n * log(m * n)) due to the binary search (log(m * n) iterations) and BFS within each iteration (O(m * n) for fire spread and O(m * n) for pathfinding in worst case).

Space Complexity: O(m * n) to store the grid, fire grid, and visited grid during BFS.

The provided code solutions in Python, Java, C++, and TypeScript implement this algorithm. They differ slightly in syntax and data structure usage, but the underlying logic remains the same. Each solution includes the spread and check functions reflecting the BFS simulations and the binary search framework for finding the optimal waiting time.