# Escape the Spreading Fire
**Difficulty:** HARD
[External](https://leetcode.com/problems/escape-the-spreading-fire)
Canonical: https://scaleengineer.com/dsa/problems/escape-the-spreading-fire
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/escape-the-spreading-fire/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/escape-the-spreading-fire/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/escape-the-spreading-fire/image2.jpg) 

**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`

# Approaches
## Linear Scan on Wait Time
A straightforward but less efficient approach is to check every possible wait time `W` linearly. We can start from a reasonable maximum possible wait time and go down to zero. The first value of `W` for which we can find a safe path to the safehouse is our answer.
**Time:** O((M*N)^2), where M and N are the dimensions of the grid. The `fireTime` calculation takes O(M*N). The main loop runs up to M*N times, and each iteration calls `canReach`, which also takes O(M*N) in the worst case. · **Space:** O(M*N) to store the `fireTime` grid, the visited array, and the queue for BFS.
**Pros:** Conceptually simple and easy to understand.; The logic for checking reachability is reusable in more optimal solutions.
**Cons:** The time complexity is high, making it likely to result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The core of this approach relies on a helper function, `canReach(W)`, which determines if it's possible to reach the safehouse given an initial wait time of `W` minutes.

First, we need to know when the fire reaches each cell. This can be pre-calculated using a multi-source Breadth-First Search (BFS) starting from all initial fire cells. Let's store these times in a `fireTime` grid. `fireTime[r][c]` will be the number of minutes it takes for fire to reach cell `(r, c)`.

With the `fireTime` grid, the `canReach(W)` function can be implemented using another BFS, this time for the player's path. The player starts at `(0, 0)` at time `W`. A path is valid if for every cell `(r, c)` on the path, the player's arrival time is less than the fire's arrival time (`fireTime[r][c]`). For the final destination, the arrival times can be equal.

The main algorithm then iterates `W` from a maximum possible value (e.g., `m * n`) down to 0. For each `W`, it calls `canReach(W)`. The first `W` that returns `true` is the maximum possible wait time.

Special cases to handle:
- If `canReach(m*n)` is true, it implies a fire-proof path exists, so we can wait indefinitely. We return `10^9`.
- If the loop finishes without finding a valid `W`, it's impossible to reach the safehouse, so we return `-1`.

```java
class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m, n;

    public int maximumMinutes(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        int[][] fireTime = new int[m][n];
        for (int[] row : fireTime) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }
        calculateFireTime(grid, fireTime);

        if (canReach(grid, fireTime, m * n)) {
            return 1_000_000_000;
        }

        for (int w = m * n - 1; w >= 0; w--) {
            if (canReach(grid, fireTime, w)) {
                return w;
            }
        }

        return -1;
    }

    private void calculateFireTime(int[][] grid, int[][] fireTime) {
        java.util.Queue<int[]> q = new java.util.LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    fireTime[i][j] = 0;
                }
            }
        }
        int time = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            time++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && fireTime[nr][nc] == Integer.MAX_VALUE) {
                        fireTime[nr][nc] = time;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
        }
    }

    private boolean canReach(int[][] grid, int[][] fireTime, int waitTime) {
        if (waitTime >= fireTime[0][0]) return false;

        java.util.Queue<int[]> q = new java.util.LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;

        int time = waitTime;
        while (!q.isEmpty()) {
            int size = q.size();
            time++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {
                        if (nr == m - 1 && nc == n - 1) {
                            if (time <= fireTime[nr][nc]) return true;
                        }
                        if (time < fireTime[nr][nc]) {
                            visited[nr][nc] = true;
                            q.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. First, pre-calculate the minimum time for fire to reach every grass cell. This is done using a multi-source BFS starting from all initial fire cells. Store these times in a `fireTime` grid.
2. Define a helper function `canReach(W)` that takes an integer `W` (wait time) and returns `true` if the safehouse is reachable, `false` otherwise.
3. The `canReach(W)` function works as follows:
  - It performs a BFS starting from `(0, 0)` to find a path for the person.
  - The initial time for the person's BFS is `W`.
  - A move to an adjacent cell `(r, c)` is valid only if the person's arrival time at that cell is strictly less than `fireTime[r][c]`. This ensures the person can move through the cell before it catches fire.
  - For the destination cell `(m-1, n-1)`, the arrival time can be less than or equal to `fireTime[m-1][n-1]`.
4. Check if `canReach(m*n)` is true. If so, it means a path immune to fire exists, and the answer is `10^9`.
5. If not, iterate `W` from `m*n - 1` down to `0`. The first `W` for which `canReach(W)` returns `true` is the maximum wait time.
6. If the loop completes without finding a solution, return `-1`.

## Binary Search on Wait Time
A more efficient approach leverages the monotonic nature of the problem. If we can safely reach the safehouse by waiting `W` minutes, we can also do so by waiting any amount of time less than `W`. This property allows us to use binary search on the wait time `W` to find the maximum possible value.
**Time:** O(M*N * log(M*N)). The `fireTime` calculation is O(M*N). The binary search performs log(M*N) iterations, and in each iteration, it calls `canReach`, which takes O(M*N). · **Space:** O(M*N) for the `fireTime` grid, visited array, and BFS queues.
**Pros:** Highly efficient and significantly faster than the linear scan approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** The logic is slightly more complex due to the addition of the binary search framework.
### Explanation
The overall structure is similar to the linear scan, but instead of checking every `W`, we use binary search to find the optimal `W` much faster.

The search space for `W` will be from `0` to a safe upper bound, like `m * n`.

1.  **Pre-computation:** Just like the previous approach, we first compute the `fireTime` grid using a multi-source BFS from all fire sources.

2.  **Binary Search:** We perform a binary search on the wait time `W` in the range `[0, m*n]`. For each `mid` value (our candidate `W`), we call the same `canReach(mid)` function to check if a safe path exists.
    - If `canReach(mid)` is `true`, it means `mid` is a possible wait time. We try for a longer wait time by setting `low = mid + 1` and storing `mid` as a potential answer.
    - If `canReach(mid)` is `false`, the wait time `mid` is too long. We need to search for a smaller `W` by setting `high = mid - 1`.

3.  **Result:** After the binary search loop terminates, the stored answer will be the maximum valid wait time. We then handle the special cases: if the answer is `m*n`, we return `10^9`; otherwise, we return the answer (which could be `-1` if no path was ever found).

```java
class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m, n;

    public int maximumMinutes(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        int[][] fireTime = new int[m][n];
        for (int[] row : fireTime) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }
        calculateFireTime(grid, fireTime);

        int low = 0, high = m * n;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canReach(grid, fireTime, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ans == m * n ? 1_000_000_000 : ans;
    }

    // The calculateFireTime and canReach methods are identical to the previous approach.
    private void calculateFireTime(int[][] grid, int[][] fireTime) {
        java.util.Queue<int[]> q = new java.util.LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    fireTime[i][j] = 0;
                }
            }
        }
        int time = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            time++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && fireTime[nr][nc] == Integer.MAX_VALUE) {
                        fireTime[nr][nc] = time;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
        }
    }

    private boolean canReach(int[][] grid, int[][] fireTime, int waitTime) {
        if (waitTime >= fireTime[0][0]) return false;

        java.util.Queue<int[]> q = new java.util.LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;

        int time = waitTime;
        while (!q.isEmpty()) {
            int size = q.size();
            time++;
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int nr = curr[0] + dir[0], nc = curr[1] + dir[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {
                        if (nr == m - 1 && nc == n - 1) {
                            if (time <= fireTime[nr][nc]) return true;
                        }
                        if (time < fireTime[nr][nc]) {
                            visited[nr][nc] = true;
                            q.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. First, pre-calculate the `fireTime` grid using a multi-source BFS, identical to the linear scan approach.
2. Recognize that the problem has a monotonic property: if waiting `W` minutes is safe, waiting `W-1` minutes is also safe. This allows for binary search on the answer.
3. Set a search range for the wait time `W`, for example, from `0` to `m*n`.
4. Initialize `low = 0`, `high = m*n`, and `ans = -1`.
5. In a loop while `low <= high`:
  - Calculate `mid = low + (high - low) / 2`.
  - Use the `canReach(mid)` function to check if it's possible to reach the safehouse with a wait time of `mid`.
  - If `canReach(mid)` is true, `mid` is a possible answer. We try for a larger wait time, so we set `ans = mid` and `low = mid + 1`.
  - If `canReach(mid)` is false, `mid` is too long. We must wait less, so we set `high = mid - 1`.
6. After the loop, if `ans` equals the initial upper bound (`m*n`), it implies we can wait indefinitely, so return `10^9`.
7. Otherwise, return `ans`. This will be the maximum valid wait time, or `-1` if no solution exists.

# Solutions
### Java

```java
class Solution {
private
  int[][] grid;
private
  boolean[][] fire;
private
  boolean[][] vis;
private
  final int[] dirs = {-1, 0, 1, 0, -1};
private
  int m;
private
  int n;
public
  int maximumMinutes(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    fire = new boolean[m][n];
    vis = new boolean[m][n];
    int l = -1, r = m * n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l == m * n ? 1000000000 : l;
  }
private
  boolean check(int t) {
    for (int i = 0; i < m; ++i) {
      Arrays.fill(fire[i], false);
      Arrays.fill(vis[i], false);
    }
    Deque<int[]> q1 = new ArrayDeque<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          q1.offer(new int[]{i, j});
          fire[i][j] = true;
        }
      }
    }
    for (; t > 0 && !q1.isEmpty(); --t) {
      q1 = spread(q1);
    }
    if (fire[0][0]) {
      return false;
    }
    Deque<int[]> q2 = new ArrayDeque<>();
    q2.offer(new int[]{0, 0});
    vis[0][0] = true;
    for (; !q2.isEmpty(); q1 = spread(q1)) {
      for (int d = q2.size(); d > 0; --d) {
        int[] p = q2.poll();
        if (fire[p[0]][p[1]]) {
          continue;
        }
        for (int k = 0; k < 4; ++k) {
          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] && !vis[x][y] &&
              grid[x][y] == 0) {
            if (x == m - 1 && y == n - 1) {
              return true;
            }
            vis[x][y] = true;
            q2.offer(new int[]{x, y});
          }
        }
      }
    }
    return false;
  }
private
  Deque<int[]> spread(Deque<int[]> q) {
    Deque<int[]> nq = new ArrayDeque<>();
    while (!q.isEmpty()) {
      int[] p = q.poll();
      for (int k = 0; k < 4; ++k) {
        int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] &&
            grid[x][y] == 0) {
          fire[x][y] = true;
          nq.offer(new int[]{x, y});
        }
      }
    }
    return nq;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumMinutes(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    bool vis[m][n];
    bool fire[m][n];
    int dirs[5] = {-1, 0, 1, 0, -1};
    auto spread = [&](queue<pair<int, int>> &q) {
      queue<pair<int, int>> nq;
      while (q.size()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && !fire[x][y] &&
              grid[x][y] == 0) {
            fire[x][y] = true;
            nq.emplace(x, y);
          }
        }
      }
      return nq;
    };
    auto check = [&](int t) {
      memset(vis, false, sizeof(vis));
      memset(fire, false, sizeof(fire));
      queue<pair<int, int>> q1;
      for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
          if (grid[i][j] == 1) {
            q1.emplace(i, j);
            fire[i][j] = true;
          }
        }
      }
      for (; t && q1.size(); --t) {
        q1 = spread(q1);
      }
      if (fire[0][0]) {
        return false;
      }
      queue<pair<int, int>> q2;
      q2.emplace(0, 0);
      vis[0][0] = true;
      for (; q2.size(); q1 = spread(q1)) {
        for (int d = q2.size(); d; --d) {
          auto [i, j] = q2.front();
          q2.pop();
          if (fire[i][j]) {
            continue;
          }
          for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
                !fire[x][y] && grid[x][y] == 0) {
              if (x == m - 1 && y == n - 1) {
                return true;
              }
              vis[x][y] = true;
              q2.emplace(x, y);
            }
          }
        }
      }
      return false;
    };
    int l = -1, r = m * n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l == m * n ? 1e9 : l;
  }
};

```

### Python

```python
class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int: def spread(q: Deque[int]) -> Deque[int]: nq = deque() while q: i, j = q . popleft() for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and not fire[x][y] and grid[x][y] == 0: fire[x][y] = True nq . append((x, y)) return nq def check(t: int) -> bool: for i in range(m): for j in range(n): fire[i][j] = False q1 = deque() for i, row in enumerate(grid): for j, x in enumerate(row): if x == 1: fire[i][j] = True q1 . append((i, j)) while t and q1: q1 = spread(q1) t -= 1 if fire[0][0]: return False q2 = deque([(0, 0)]) vis = [[False] * n for _ in range(m)] vis[0][0] = True while q2: for _ in range(len(q2)): i, j = q2 . popleft() if fire[i][j]: continue for a, b in pairwise(dirs): x, y = i + a, j + b if (0 <= x < m and 0 <= y < n and not vis[x][y] and not fire[x][y] and grid[x][y] == 0): if x == m - 1 and y == n - 1: return True vis[x][y] = True q2 . append((x, y)) q1 = spread(q1) return False m, n = len(grid), len(grid[0]) l, r = - 1, m * n dirs = (- 1, 0, 1, 0, - 1) fire = [[False] * n for _ in range(m)] while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return int(1e9) if l == m * n else l

```