LeetCode 2814 - Minimum Time Takes to Reach Destination Without Drowning

This problem takes place on a two-dimensional grid where each cell represents a type of terrain. The grid contains: - "S": your starting position. - "D": the destination you want to reach. - ".": an empty cell that can be walked on. - "X": a stone cell that cannot be entered.

leetcodehardarraybreadth-first-searchmatrix

LeetCode Problem 2814

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Matrix

Solution

LeetCode 2814 - Minimum Time Takes to Reach Destination Without Drowning

Problem Understanding

This problem takes place on a two-dimensional grid where each cell represents a type of terrain.

The grid contains:

  • "S": your starting position.
  • "D": the destination you want to reach.
  • ".": an empty cell that can be walked on.
  • "X": a stone cell that cannot be entered.
  • "*": a flooded cell.

Every second, two things happen conceptually:

  1. You may move one step in one of the four cardinal directions.
  2. Flood water spreads from every flooded cell into adjacent empty cells.

The critical rule is that you cannot enter a flooded cell. Furthermore, you cannot move into a cell at the exact moment it becomes flooded. If a cell floods at time t, then arriving there at time t is already too late.

The destination cell is special because the problem guarantees that it will never be flooded. Water only spreads into empty cells (".").

The goal is to determine the minimum number of seconds required to travel from S to D while always staying ahead of the flood. If no safe path exists, we return -1.

Understanding the Constraints

The grid dimensions satisfy:

  • 2 <= n, m <= 100

This means the grid contains at most:

100 * 100 = 10,000 cells

A graph traversal that visits each cell a constant number of times is completely feasible.

The relatively small grid size strongly suggests a Breadth-First Search solution because BFS naturally computes shortest paths in unweighted grids.

Important Edge Cases

Several situations can cause incorrect solutions:

  • The shortest geometric path may become unusable because water reaches it first.
  • Multiple flooded cells spread simultaneously, so we must model all water sources together.
  • A cell that floods at time t cannot be entered at time t.
  • The destination may be surrounded by water or stones even though it never floods itself.
  • The start position might become trapped immediately.
  • There may be no flood cells at all, reducing the problem to a standard shortest-path search.

The guarantee that exactly one S and one D exist simplifies parsing the grid.

Approaches

Brute Force

A naive approach would explicitly simulate the world second by second.

At each time step:

  1. Spread the flood.
  2. Track every position the player could currently occupy.
  3. Continue until either the destination is reached or no positions remain.

This eventually produces the correct answer because it accurately models the process. However, the state space grows over time, and repeatedly updating the flood for every second introduces unnecessary work.

The main inefficiency is that flood timing is recomputed over and over. We only care about the earliest moment each cell becomes flooded.

Key Insight

Instead of simulating both processes simultaneously, we can separate them.

The crucial observation is that flood propagation is independent of the player's movement.

First, compute:

floodTime[r][c]

which stores the earliest second when each cell becomes flooded.

This can be found using a multi-source BFS starting from every "*" cell.

After we know flood arrival times, we perform another BFS from the start position.

When attempting to move into a cell at time t + 1:

  • The cell must not be a stone.
  • The cell must not already be flooded.
  • The cell must not flood at time t + 1.

In other words:

arrivalTime < floodTime

must hold.

Once flood arrival times are known, the remaining problem becomes a shortest-path search with timing constraints.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((nm)^2) in the worst case O(nm) Repeatedly simulates flood spreading and player movement
Optimal O(nm) O(nm) Two BFS traversals, one for flood and one for player

Algorithm Walkthrough

Step 1: Locate special cells

Scan the grid once and identify:

  • Start position S
  • Destination position D
  • Every flooded source *

All flood sources are inserted into a queue for the first BFS.

Step 2: Compute flood arrival times

Create a matrix:

floodTime[r][c]

initialized to infinity.

For every flooded source:

floodTime[source] = 0

Run a multi-source BFS.

Whenever water reaches an adjacent empty cell for the first time:

floodTime[next] = floodTime[current] + 1

Important details:

  • Water cannot enter stones.
  • Water cannot enter the destination.
  • Water only spreads into "." cells.

At the end, every reachable empty cell knows exactly when it floods.

Step 3: Perform BFS from the start

Create another queue containing:

(startRow, startCol, 0)

where the third value is elapsed time.

Maintain a visited matrix so each cell is processed once.

Step 4: Explore neighbors

For each state:

(row, col, currentTime)

consider the four neighboring cells.

The arrival time becomes:

nextTime = currentTime + 1

A move is allowed if:

  1. The cell is inside the grid.
  2. The cell is not a stone.
  3. The cell has not been visited.
  4. The cell is the destination, or
  5. nextTime < floodTime[nextRow][nextCol].

The strict inequality is critical because arriving at the exact flooding moment means drowning.

Step 5: Return when destination is reached

Because BFS explores states in increasing order of time, the first time we reach D is guaranteed to be the minimum travel time.

Return that value immediately.

Step 6: Handle failure

If BFS finishes without reaching the destination, return:

-1

Why it works

The first BFS computes the earliest flooding time for every cell. Since BFS explores in increasing distance order and all flood sources start simultaneously, the recorded value is exactly the first second when water reaches that cell.

The second BFS explores all safe paths in increasing order of travel time. A move is permitted only if the traveler arrives strictly before the flood. Therefore every state processed by the BFS represents a valid position at that moment in time. Since BFS always finds the shortest path in an unweighted graph, the first time the destination is reached is the minimum safe travel time.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumSeconds(self, land: List[List[str]]) -> int:
        rows, cols = len(land), len(land[0])

        INF = 10**9
        flood_time = [[INF] * cols for _ in range(rows)]

        flood_queue = deque()
        start = None
        destination = None

        for r in range(rows):
            for c in range(cols):
                if land[r][c] == "*":
                    flood_time[r][c] = 0
                    flood_queue.append((r, c))
                elif land[r][c] == "S":
                    start = (r, c)
                elif land[r][c] == "D":
                    destination = (r, c)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Multi-source BFS for flood spread.
        while flood_queue:
            r, c = flood_queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if not (0 <= nr < rows and 0 <= nc < cols):
                    continue

                if land[nr][nc] != ".":
                    continue

                if flood_time[nr][nc] != INF:
                    continue

                flood_time[nr][nc] = flood_time[r][c] + 1
                flood_queue.append((nr, nc))

        sr, sc = start
        dr, dc = destination

        queue = deque([(sr, sc, 0)])
        visited = [[False] * cols for _ in range(rows)]
        visited[sr][sc] = True

        while queue:
            r, c, time = queue.popleft()

            if (r, c) == (dr, dc):
                return time

            for drow, dcol in directions:
                nr, nc = r + drow, c + dcol

                if not (0 <= nr < rows and 0 <= nc < cols):
                    continue

                if visited[nr][nc]:
                    continue

                if land[nr][nc] == "X":
                    continue

                next_time = time + 1

                if land[nr][nc] == "D":
                    visited[nr][nc] = True
                    queue.append((nr, nc, next_time))
                    continue

                if next_time >= flood_time[nr][nc]:
                    continue

                visited[nr][nc] = True
                queue.append((nr, nc, next_time))

        return -1

Implementation Explanation

The first section scans the grid and gathers all flooded cells, the start position, and the destination.

The flood_time matrix stores the earliest flooding time for every cell. A multi-source BFS begins with all flood sources simultaneously. Because every source starts at time zero, BFS naturally computes the minimum flooding time for each reachable empty cell.

After flood timing is known, a second BFS searches for the traveler's shortest safe route. Each queue entry contains the current position and elapsed time.

When moving into a neighboring cell, the algorithm computes the arrival time and checks whether that time is strictly less than the flood arrival time. This enforces the rule that entering a cell exactly when it floods is not allowed.

Since BFS explores states by increasing time, the first visit to the destination is the optimal answer.

Go Solution

package main

import "container/list"

func minimumSeconds(land [][]string) int {
	rows := len(land)
	cols := len(land[0])

	const INF = int(1e9)

	floodTime := make([][]int, rows)
	for i := range floodTime {
		floodTime[i] = make([]int, cols)
		for j := range floodTime[i] {
			floodTime[i][j] = INF
		}
	}

	type Cell struct {
		r int
		c int
	}

	floodQueue := list.New()

	var startR, startC int
	var destR, destC int

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			switch land[r][c] {
			case "*":
				floodTime[r][c] = 0
				floodQueue.PushBack(Cell{r, c})
			case "S":
				startR, startC = r, c
			case "D":
				destR, destC = r, c
			}
		}
	}

	dirs := [][2]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	for floodQueue.Len() > 0 {
		front := floodQueue.Front()
		floodQueue.Remove(front)

		cur := front.Value.(Cell)

		for _, d := range dirs {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				continue
			}

			if land[nr][nc] != "." {
				continue
			}

			if floodTime[nr][nc] != INF {
				continue
			}

			floodTime[nr][nc] = floodTime[cur.r][cur.c] + 1
			floodQueue.PushBack(Cell{nr, nc})
		}
	}

	type State struct {
		r    int
		c    int
		time int
	}

	queue := list.New()
	queue.PushBack(State{startR, startC, 0})

	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}
	visited[startR][startC] = true

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		cur := front.Value.(State)

		if cur.r == destR && cur.c == destC {
			return cur.time
		}

		for _, d := range dirs {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				continue
			}

			if visited[nr][nc] {
				continue
			}

			if land[nr][nc] == "X" {
				continue
			}

			nextTime := cur.time + 1

			if land[nr][nc] == "D" {
				visited[nr][nc] = true
				queue.PushBack(State{nr, nc, nextTime})
				continue
			}

			if nextTime >= floodTime[nr][nc] {
				continue
			}

			visited[nr][nc] = true
			queue.PushBack(State{nr, nc, nextTime})
		}
	}

	return -1
}

Go-Specific Notes

The Go solution mirrors the Python algorithm exactly. Since Go does not provide a built-in deque, container/list is used as the BFS queue. The flood timing matrix is initialized with a large sentinel value (1e9) representing infinity. All time values remain well within Go's integer range because the grid contains at most 10,000 cells.

Worked Examples

Example 1

D . *
. . .
. S .

Flood BFS

Cell Flood Time
(0,2) 0
(0,1) 1
(1,2) 1
(0,0) 2
(1,1) 2
(2,2) 2
(1,0) 3
(2,1) 3
(2,0) 4

Destination is not flooded.

Person BFS

Time Reachable Position
0 (2,1)
1 (2,0), (1,1)
2 (1,0)
3 (0,0)=D

Answer:

3

Example 2

D X *
. . .
. . S

Flood Times

Cell Flood Time
(0,2) 0
(1,2) 1
(1,1) 2
(2,2) 2
(1,0) 3
(2,1) 3
(2,0) 4

Any route toward the destination requires entering cells that flood before or at arrival time.

Result:

-1

Example 3

D . . . * .
. X . X . .
. . . . S .

The flood BFS computes the earliest flooding times throughout the grid.

The traveler BFS then explores all safe positions in increasing travel time order.

The shortest safe route reaches the destination after:

6 seconds

Therefore the answer is:

6

Complexity Analysis

Measure Complexity Explanation
Time O(nm) Each BFS visits every cell at most once
Space O(nm) Flood matrix, visited matrix, and BFS queues

Both BFS traversals process each cell at most one time. Since the grid contains n * m cells, the total running time is linear in the size of the grid. The auxiliary memory consists primarily of the flood timing matrix, the visited matrix, and the queues, all of which require linear space.

Test Cases

sol = Solution()

assert sol.minimumSeconds([
    ["D", ".", "*"],
    [".", ".", "."],
    [".", "S", "."]
]) == 3  # Example 1

assert sol.minimumSeconds([
    ["D", "X", "*"],
    [".", ".", "."],
    [".", ".", "S"]
]) == -1  # Example 2

assert sol.minimumSeconds([
    ["D", ".", ".", ".", "*", "."],
    [".", "X", ".", "X", ".", "."],
    [".", ".", ".", ".", "S", "."]
]) == 6  # Example 3

assert sol.minimumSeconds([
    ["D", "."],
    ["S", "."]
]) == 1  # No flood, direct path

assert sol.minimumSeconds([
    ["D", ".", "."],
    ["X", "X", "."],
    ["S", ".", "."]
]) == 4  # Must travel around obstacles

assert sol.minimumSeconds([
    ["D", ".", "*"],
    ["X", "X", "."],
    ["S", ".", "."]
]) == -1  # Flood blocks all routes

assert sol.minimumSeconds([
    ["D", "."],
    [".", "S"]
]) == 1  # Smallest practical grid

assert sol.minimumSeconds([
    ["D", ".", ".", "."],
    [".", "X", "X", "."],
    [".", ".", ".", "."],
    ["S", ".", ".", "*"]
]) == -1  # Destination unreachable before flood

assert sol.minimumSeconds([
    ["D", ".", ".", "."],
    [".", ".", ".", "."],
    [".", ".", ".", "."],
    ["S", ".", ".", "."]
]) == 3  # No flood, shortest path BFS

Test Summary

Test Why
Example 1 Basic successful escape
Example 2 Flood overtakes every path
Example 3 Larger grid with obstacles and flood
No flood direct path Reduces to ordinary BFS
Obstacle detour Verifies shortest-path behavior
Flood blocks route Tests timing constraints
Smallest practical grid Boundary dimensions
Flood near destination Ensures safe arrival checks
Empty open grid Standard shortest path

Edge Cases

Arriving Exactly When a Cell Floods

One of the easiest mistakes is allowing a move into a cell at the same second that water arrives. The problem explicitly forbids this. If a cell floods at time 5, arriving at time 5 means drowning.

The implementation enforces:

arrivalTime < floodTime

instead of:

arrivalTime <= floodTime

which correctly handles this subtle rule.

Multiple Flood Sources

Flood may start from several locations simultaneously. Running a separate BFS from each flood source would be inefficient and could produce complicated logic for combining results.

The multi-source BFS begins with every "*" cell already in the queue at time 0. This naturally computes the earliest flood arrival time for every location.

Destination Adjacent to Flood

The destination never floods, but neighboring cells can. A naive implementation might incorrectly propagate water into the destination or require a flood-time check before entering it.

The solution treats "D" specially. During flood BFS, water never enters the destination. During traveler BFS, reaching "D" is always allowed as long as the move itself is valid.

Start Position Becoming Trapped

Sometimes the traveler begins with several available moves, but every neighboring cell floods too quickly. A path may exist geometrically yet still be impossible temporally.

Because every move is checked against the precomputed flood arrival times, unsafe moves are rejected immediately. If no valid states remain in the BFS queue, the algorithm correctly returns -1.