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

Minimum Time Takes to Reach Destination Without Drowning

Number: 3043

Difficulty: Hard

Paid? Yes

Companies: Wix

Problem Description

You are given an n x m grid where each cell represents a type of terrain. The grid contains:

  • "S": the starting cell
  • "D": the destination cell (which will never be flooded)
  • ".": an empty cell where you can move
  • "X": a stone cell that cannot be stepped on
  • "*": a flooded cell

Each second, you can move to one of the four adjacent cells (up, down, left, right) provided that the cell is not a stone or flooded. In the same second, the water floods any empty cell adjacent to a flooded cell. Note that you cannot move onto a cell that is flooded or will be flooded in that same second.

Return the minimum number of seconds required to reach the destination "D" from "S". If it is impossible, return -1.

Key Insights

  • Use a multi-step Breadth-First Search (BFS) approach.
  • First, simulate the flood spread: perform a multi-source BFS starting from all initially flooded cells to compute the time each empty cell gets flooded.
  • Then, perform a BFS from the starting cell "S", ensuring that you only move into cells that are not currently flooded or will be flooded at the time of arrival (i.e., arrival time must be strictly less than the flood time for that cell).
  • Carefully handle boundaries and obstacles ("X" cells) to avoid invalid moves.

Space and Time Complexity

Time Complexity: O(nm) — each cell is processed a constant number of times in both flood and path BFS. Space Complexity: O(nm) — additional space for the flood time grid and BFS queue.

Solution

We use two BFS traversals:

  1. Flood Spread BFS: Start from all cells initially marked "*" and compute the earliest time each empty cell (".") can get flooded. The resulting "flood_time" matrix helps decide if a cell is safe to move into at a given time during the path search.
  2. Path BFS: Starting from "S", we explore all possible moves, making sure that when moving to a cell at time t+1, that cell’s flood time is either not set (meaning it will not flood) or t+1 is strictly less than the flood time. This ensures the safe arrival.

This combined approach ensures that we are always aware of both the flood spread dynamics and the allowed moves for the person.

Code Solutions

from collections import deque

def minimum_time_to_destination(land):
    n = len(land)
    m = len(land[0])
    # Initialize flood times with -1 (indicating not flooded)
    flood_time = [[-1] * m for _ in range(n)]
    q = deque()

    # Initialize starting positions for flood BFS and locate S and D
    start = None
    for i in range(n):
        for j in range(m):
            if land[i][j] == "*":
                flood_time[i][j] = 0
                q.append((i, j, 0))  # (row, col, time)
            elif land[i][j] == "S":
                start = (i, j)
    
    # Directions: up, down, left, right
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    # Flood spread BFS
    while q:
        i, j, t = q.popleft()
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m:
                # Flood spreads only to empty cells and starting point cell "S"
                if land[ni][nj] in [".", "S"] and flood_time[ni][nj] == -1:
                    flood_time[ni][nj] = t + 1
                    q.append((ni, nj, t + 1))
    
    # Setup BFS from starting point S
    si, sj = start
    # use visited matrix to track steps 
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((si, sj, 0))
    visited[si][sj] = True

    while q:
        i, j, t = q.popleft()
        # If destination reached
        if land[i][j] == "D":
            return t
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj]:
                # Can't go to stone cell
                if land[ni][nj] == "X":
                    continue
                nt = t + 1
                # Check if cell is safe: either not flooded ever or we arrive before it floods
                if flood_time[ni][nj] != -1 and nt >= flood_time[ni][nj]:
                    continue
                visited[ni][nj] = True
                q.append((ni, nj, nt))
    return -1

# Example usage:
land1 = [["D",".","*"],[".",".","."],[".", "S", "."]]
print(minimum_time_to_destination(land1))  # Output: 3
← Back to All Questions