Minimum Time Takes to Reach Destination Without Drowning

Problem#

A grid contains S (start), D (destination), . (land), * (water source), and X (blocked). Water spreads to adjacent land cells every minute. You move one step per minute. You can’t step into a flooded cell. Return the minimum time to reach D, or -1.

Examples#

grid = [["D",".","*"],[".",".","."],[".","S","."]] → 3
grid = [["D","X","*"],[".",".","."],[".",".","S"]] → -1

Constraints#

2 <= m, n <= 100. There is exactly one S and one D.

Approach#

Multi-source BFS from all water cells to compute the earliest flood time per cell. Then BFS from S: at step t+1, only enter a neighbor if its flood time is strictly greater than t+1 (or it’s D).

Solution#

class Solution {
public:
    int minimumSeconds(vector<vector<string>>& land) {
        int m = land.size(), n = land[0].size();
        const int INF = INT_MAX;
        vector<vector<int>> flood(m, vector<int>(n, INF));
        queue<pair<int,int>> q;
        int sr = 0, sc = 0, dr = 0, dc = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == "*") { flood[i][j] = 0; q.push({i, j}); }
                else if (land[i][j] == "S") { sr = i; sc = j; }
                else if (land[i][j] == "D") { dr = i; dc = j; }
            }
        }
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int k = 0; k < 4; ++k) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (land[nr][nc] == "X" || land[nr][nc] == "D") continue;
                if (flood[nr][nc] != INF) continue;
                flood[nr][nc] = flood[r][c] + 1;
                q.push({nr, nc});
            }
        }
        vector<vector<int>> dist(m, vector<int>(n, -1));
        dist[sr][sc] = 0;
        queue<pair<int,int>> p;
        p.push({sr, sc});
        while (!p.empty()) {
            auto [r, c] = p.front(); p.pop();
            int t = dist[r][c];
            for (int k = 0; k < 4; ++k) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (land[nr][nc] == "X") continue;
                if (dist[nr][nc] != -1) continue;
                int nt = t + 1;
                if (land[nr][nc] == "D") return nt;
                if (nt < flood[nr][nc]) {
                    dist[nr][nc] = nt;
                    p.push({nr, nc});
                }
            }
        }
        return -1;
    }
};

func minimumSeconds(land [][]string) int {
    m, n := len(land), len(land[0])
    INF := math.MaxInt32
    flood := make([][]int, m)
    for i := range flood {
        flood[i] = make([]int, n)
        for j := range flood[i] {
            flood[i][j] = INF
        }
    }
    type pt struct{ r, c int }
    var q []pt
    sr, sc, dr, dc := 0, 0, 0, 0
    _ = dr
    _ = dc
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch land[i][j] {
            case "*":
                flood[i][j] = 0
                q = append(q, pt{i, j})
            case "S":
                sr, sc = i, j
            case "D":
                dr, dc = i, j
            }
        }
    }
    dx := [4]int{1, -1, 0, 0}
    dy := [4]int{0, 0, 1, -1}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        r, c := cur.r, cur.c
        for k := 0; k < 4; k++ {
            nr, nc := r+dx[k], c+dy[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            if land[nr][nc] == "X" || land[nr][nc] == "D" {
                continue
            }
            if flood[nr][nc] != INF {
                continue
            }
            flood[nr][nc] = flood[r][c] + 1
            q = append(q, pt{nr, nc})
        }
    }
    dist := make([][]int, m)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = -1
        }
    }
    dist[sr][sc] = 0
    p := []pt{{sr, sc}}
    for len(p) > 0 {
        cur := p[0]
        p = p[1:]
        r, c := cur.r, cur.c
        t := dist[r][c]
        for k := 0; k < 4; k++ {
            nr, nc := r+dx[k], c+dy[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            if land[nr][nc] == "X" {
                continue
            }
            if dist[nr][nc] != -1 {
                continue
            }
            nt := t + 1
            if land[nr][nc] == "D" {
                return nt
            }
            if nt < flood[nr][nc] {
                dist[nr][nc] = nt
                p = append(p, pt{nr, nc})
            }
        }
    }
    return -1
}

from collections import deque
from typing import List

class Solution:
    def minimumSeconds(self, land: List[List[str]]) -> int:
        m, n = len(land), len(land[0])
        INF = float('inf')
        flood = [[INF] * n for _ in range(m)]
        q: deque = deque()
        sr = sc = 0
        for i in range(m):
            for j in range(n):
                if land[i][j] == "*":
                    flood[i][j] = 0
                    q.append((i, j))
                elif land[i][j] == "S":
                    sr, sc = i, j
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while q:
            r, c = q.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if land[nr][nc] in ("X", "D"):
                    continue
                if flood[nr][nc] != INF:
                    continue
                flood[nr][nc] = flood[r][c] + 1
                q.append((nr, nc))
        dist = [[-1] * n for _ in range(m)]
        dist[sr][sc] = 0
        p: deque = deque([(sr, sc)])
        while p:
            r, c = p.popleft()
            t = dist[r][c]
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if land[nr][nc] == "X":
                    continue
                if dist[nr][nc] != -1:
                    continue
                nt = t + 1
                if land[nr][nc] == "D":
                    return nt
                if nt < flood[nr][nc]:
                    dist[nr][nc] = nt
                    p.append((nr, nc))
        return -1

function minimumSeconds(land) {
    const m = land.length, n = land[0].length;
    const INF = Infinity;
    const flood = Array.from({ length: m }, () => new Array(n).fill(INF));
    let sr = 0, sc = 0;
    const q = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (land[i][j] === '*') {
                flood[i][j] = 0;
                q.push([i, j]);
            } else if (land[i][j] === 'S') {
                sr = i; sc = j;
            }
        }
    }
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let head = 0;
    while (head < q.length) {
        const [r, c] = q[head++];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (land[nr][nc] === 'X' || land[nr][nc] === 'D') continue;
            if (flood[nr][nc] !== INF) continue;
            flood[nr][nc] = flood[r][c] + 1;
            q.push([nr, nc]);
        }
    }
    const dist = Array.from({ length: m }, () => new Array(n).fill(-1));
    dist[sr][sc] = 0;
    const p = [[sr, sc]];
    let ph = 0;
    while (ph < p.length) {
        const [r, c] = p[ph++];
        const t = dist[r][c];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (land[nr][nc] === 'X') continue;
            if (dist[nr][nc] !== -1) continue;
            const nt = t + 1;
            if (land[nr][nc] === 'D') return nt;
            if (nt < flood[nr][nc]) {
                dist[nr][nc] = nt;
                p.push([nr, nc]);
            }
        }
    }
    return -1;
}

class Solution {
    public int minimumSeconds(List<List<String>> land) {
        int m = land.size(), n = land.get(0).size();
        int INF = Integer.MAX_VALUE;
        int[][] flood = new int[m][n];
        for (int[] row : flood) Arrays.fill(row, INF);
        ArrayDeque<int[]> q = new ArrayDeque<>();
        int sr = 0, sc = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                String cell = land.get(i).get(j);
                if (cell.equals("*")) {
                    flood[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else if (cell.equals("S")) {
                    sr = i; sc = j;
                }
            }
        }
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                String cell = land.get(nr).get(nc);
                if (cell.equals("X") || cell.equals("D")) continue;
                if (flood[nr][nc] != INF) continue;
                flood[nr][nc] = flood[r][c] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        dist[sr][sc] = 0;
        ArrayDeque<int[]> p = new ArrayDeque<>();
        p.offer(new int[]{sr, sc});
        while (!p.isEmpty()) {
            int[] cur = p.poll();
            int r = cur[0], c = cur[1];
            int t = dist[r][c];
            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                String cell = land.get(nr).get(nc);
                if (cell.equals("X")) continue;
                if (dist[nr][nc] != -1) continue;
                int nt = t + 1;
                if (cell.equals("D")) return nt;
                if (nt < flood[nr][nc]) {
                    dist[nr][nc] = nt;
                    p.offer(new int[]{nr, nc});
                }
            }
        }
        return -1;
    }
}

function minimumSeconds(land: string[][]): number {
    const m = land.length, n = land[0].length;
    const INF = Infinity;
    const flood: number[][] = Array.from({ length: m }, () => new Array<number>(n).fill(INF));
    let sr = 0, sc = 0;
    const q: [number, number][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (land[i][j] === '*') {
                flood[i][j] = 0;
                q.push([i, j]);
            } else if (land[i][j] === 'S') {
                sr = i; sc = j;
            }
        }
    }
    const dirs: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let head = 0;
    while (head < q.length) {
        const [r, c] = q[head++];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (land[nr][nc] === 'X' || land[nr][nc] === 'D') continue;
            if (flood[nr][nc] !== INF) continue;
            flood[nr][nc] = flood[r][c] + 1;
            q.push([nr, nc]);
        }
    }
    const dist: number[][] = Array.from({ length: m }, () => new Array<number>(n).fill(-1));
    dist[sr][sc] = 0;
    const p: [number, number][] = [[sr, sc]];
    let ph = 0;
    while (ph < p.length) {
        const [r, c] = p[ph++];
        const t = dist[r][c];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (land[nr][nc] === 'X') continue;
            if (dist[nr][nc] !== -1) continue;
            const nt = t + 1;
            if (land[nr][nc] === 'D') return nt;
            if (nt < flood[nr][nc]) {
                dist[nr][nc] = nt;
                p.push([nr, nc]);
            }
        }
    }
    return -1;
}

Editorial#

Decoupling water spread (a static BFS that respects walls and treats D as un-floodable per problem variant) from player movement makes the second BFS a simple shortest-path with a per-cell forbidden timestamp. The strict inequality nt < flood[nr][nc] enforces “arrive before water does”.

Complexity#

Time: O(m*n).
Space: O(m*n).

Concept revision#

Rotting Oranges