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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Escape the Spreading Fire

Difficulty: Hard

Problem Description

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, and 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 10^9.

Key Insights

  • The problem involves a dynamic interaction between your movement and fire spread.
  • Fire spreads to all adjacent non-wall cells after each of your moves.
  • We need to determine the maximum delay before starting to move while still ensuring a safe path to the destination.
  • The scenario can be modeled with BFS (Breadth-First Search) for both your pathfinding and fire spread.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) - due to BFS and binary search on the time delay.
Space Complexity: O(m * n) - for the grid and BFS queue.

Solution

To solve this problem, we can utilize a two-phase approach:

  1. Fire Spread Simulation: First, we perform a BFS from all fire cells to calculate the time it takes for the fire to reach each cell in the grid. This will give us a fire_time grid that indicates the earliest time fire can reach each cell.

  2. Binary Search on Delay: Next, we perform a binary search on the possible delays (from 0 to 10^9) to find the maximum time we can stay at the starting position. For each potential delay, we simulate your movement using BFS, checking if you can reach the safehouse before the fire does.

This approach leverages BFS for pathfinding and fire spread, ensuring we efficiently check the necessary conditions.

Code Solutions

from collections import deque

def maximumMinutes(grid):
    m, n = len(grid), len(grid[0])
    fire_time = [[float('inf')] * n for _ in range(m)]
    
    # BFS for fire spread
    fire_queue = deque()
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                fire_queue.append((i, j))
                fire_time[i][j] = 0

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while fire_queue:
        x, y = fire_queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and fire_time[nx][ny] == float('inf'):
                fire_time[nx][ny] = fire_time[x][y] + 1
                fire_queue.append((nx, ny))

    # Check if we can reach the safehouse with a given delay
    def canReach(delay):
        if fire_time[0][0] <= delay:
            return False
        player_queue = deque([(0, 0)])
        visited = [[False] * n for _ in range(m)]
        visited[0][0] = True
        
        while player_queue:
            x, y = player_queue.popleft()
            if x == m - 1 and y == n - 1:
                return True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 0:
                    if fire_time[nx][ny] > fire_time[x][y] + 1 + delay:
                        visited[nx][ny] = True
                        player_queue.append((nx, ny))
        
        return False

    # Binary search for the maximum delay
    left, right = 0, 10**9
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if canReach(mid):
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    
    if result == 10**9:
        return 10**9
    return result
← Back to All Questions