We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Escape the Spreading Fire

Number: 2344

Difficulty: Hard

Paid? No

Companies: Google, Uber

Problem Description

Given an m x n grid where 0 represents grass, 1 represents fire, and 2 represents a wall, you start at the top-left cell (0,0) and must reach the safehouse at the bottom-right cell (m-1, n-1) by moving to adjacent grass cells. After each move you make, all fire cells spread to their adjacent (non-wall) cells. Determine the maximum number of minutes you can wait in your initial cell before starting your journey such that you still safely reach the safehouse. If it is impossible to reach the safehouse even when moving immediately, return -1. If you can always reach safely regardless of the waiting time, return 10^9.

Key Insights

  • Compute the earliest time each cell will catch fire by performing a multi-source BFS starting from all fire cells.
  • Run a separate BFS for your movement starting from (0, 0) after a given waiting time, ensuring you move only into cells that haven’t yet caught fire. (For intermediate cells, you must arrive before the fire; for the destination, arriving at the same time as the fire is allowed.)
  • Use binary search on the waiting time t (from 0 to 10^9) to determine the maximum delay for which escape is possible.
  • Handle edge cases: if you cannot escape when moving immediately, return -1; if even with a delay of 10^9 you can escape, return 10^9.

Space and Time Complexity

Time Complexity: O(m * n * log(MaxTime)) where each BFS runs in O(m*n) and binary search takes O(log(MaxTime)) steps. Space Complexity: O(m * n) for the fire time grid and additional data structures used in BFS.

Solution

We first precompute the earliest time that fire reaches each cell using a multi-source BFS from all fire cells. For each candidate waiting time, we simulate your movement using BFS starting from cell (0,0) and checking that each visited cell is reached before the fire (or, in the case of the destination, no later than the fire arrival time). If you can safely reach the destination with a given waiting time, then it is feasible. We use binary search over possible waiting times to find the maximum delay for which escape is possible. Special conditions are handled by returning -1 if immediate escape is impossible, or 10^9 if even a long delay is tolerated.

Code Solutions

import collections

def maximumMinutes(grid):
    m, n = len(grid), len(grid[0])
    # Directions: down, up, right, left.
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # Compute earliest time for fire to reach each cell.
    fireTime = [[float('inf')] * n for _ in range(m)]
    queue = collections.deque()
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                fireTime[i][j] = 0
                queue.append((i, j))
    while queue:
        x, y = queue.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 2:
                if fireTime[nx][ny] > fireTime[x][y] + 1:
                    fireTime[nx][ny] = fireTime[x][y] + 1
                    queue.append((nx, ny))
    
    # Helper function to determine if you can escape with waiting time waitTime.
    def canEscape(waitTime):
        if waitTime >= fireTime[0][0]:
            return False
        visited = [[False] * n for _ in range(m)]
        personQueue = collections.deque()
        personQueue.append((0, 0, waitTime))  # (x, y, current_time)
        visited[0][0] = True
        
        while personQueue:
            x, y, curTime = personQueue.popleft()
            if x == m - 1 and y == n - 1:
                if curTime <= fireTime[x][y]:
                    return True
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                newTime = curTime + 1
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] != 2:
                    # For normal cells, you must strictly beat the fire (newTime < fireTime).
                    # At destination, arriving at the same time is allowed.
                    if newTime < fireTime[nx][ny] or (nx == m - 1 and ny == n - 1 and newTime <= fireTime[nx][ny]):
                        visited[nx][ny] = True
                        personQueue.append((nx, ny, newTime))
        return False

    if not canEscape(0):
        return -1
    if canEscape(10**9):
        return 10**9
    
    lo, hi, ans = 0, 10**9, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if canEscape(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# Example usage
grid1 = [[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]]
print(maximumMinutes(grid1))
← Back to All Questions