< Back





2258. Escape the Spreading Fire

Did I mention how much I love graph questions?

This one gives us a 2D matrix where 0 represents grass, 1 represents fire, and 2 represents a wall.
During each tick in time, t, the fire spreads from its starting point to all adjacent cells, left,
right, up, and down. We're asked to start at (0, 0) and make our way to the safehouse at
(m - 1, n - 1) before the fire burns us. We're asked: how long can we wait before we're no longer
able to reach the safehouse?

Solving this with binary search, first we'll use BFS to determine at what time each cell in the
matrix is covered with fire. This will be our dist[][] matrix. We'll search from 0 to 10 ** 9, the
maximum amount of time we can wait.

For each step in the search, we select a time we'll wait. We conduct BFS with this time, starting
from (0, 0), only visiting cells that are grass, 0, and not on fire. What does not on fire mean?
It means that, from some time, t, we will reach the next cell before the fire does. This is defined
by dist[ny][nx], where (ny, nx) is the next cell. Reaching the next cell before the fire does means
we'll get there at time t + 1, and the fire will still be at least t + 2 away.

If we can make it to the end without getting burnt, we know we're not waiting long enough, so we
decrease the left side of our search space. Vice versa, if we are getting burnt by waiting too long,
we decrease the right side of our search space.

Eventually, we return the maximum time we can wait before running towards the safehouse. If the fire
never reaches the safe house, we can wait 10 ** 9 minutes. If there is no route to the safe house
without getting burnt, we'll return -1 by default.

The solution is as follows:


  class Solution:
      def maximumMinutes(self, grid: List[List[int]]) -> int:
          directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
          m, n = len(grid), len(grid[0])
          starts = []

          def is_valid(y: int, x: int) -> bool:
              return -1 < y < m and -1 < x < n

          dist = [[float("inf")] * n for _ in range(m)]
          seen = set()

          for i in range(m):
              for j in range(n):
                  if grid[i][j] == 1:
                      starts.append((i, j, 0))
                      seen.add((i, j))
                      dist[i][j] = 0

          queue = starts

          while queue:
              curr_queue, queue = queue, []

              for y, x, z in curr_queue:
                  for dy, dx in directions:
                      ny, nx = y + dy, x + dx

                      if is_valid(ny, nx) and not grid[ny][nx] and (ny, nx) not in seen:
                          queue.append((ny, nx, z + 1))
                          seen.add((ny, nx))
                          dist[ny][nx] = z + 1

          def bfs(t: int) -> bool:
              queue = [(0, 0, t)]
              seen = set((0, 0))

              while queue:
                  curr_queue, queue = queue, []

                  for y, x, z in curr_queue:
                      for dy, dx in directions:
                          ny, nx = y + dy, x + dx

                          if is_valid(ny, nx) and (ny, nx) not in seen and not grid[ny][nx]:
                              if (ny, nx) == (m - 1, n - 1) and dist[ny][nx] >= z + 1:
                                  return True

                              if dist[ny][nx] > z + 1:
                                  queue.append((ny, nx, z + 1))
                                  seen.add((ny, nx))

              return False

          l, r, ans = 0, 10 ** 9, -1

          while l <= r:
              mid = (r + l) // 2

              if bfs(mid):
                  ans = mid
                  l = mid + 1
              else:
                  r = mid - 1

          return ans


_ Time Complexity:

  O(m * n log(10 ** 9)) - Where m and n are the row and col dimensions of the matrix. We perform
  binary search 10 ** 9 times, the maximum number of minutes we can wait. BFS takes O(m * n) time.

_ Space Complexity:

  O(m * n) - During BFS, we have at most m * n cells in the queue.