Minimum Time Takes to Reach Destination Without Drowning

Problem

You are given an n * m 0-indexed grid of string land. Right now, you are standing at the cell that contains "S", and you want to get to the cell containing "D". There are three other types of cells in this land:

".": These cells are empty.
"X": These cells are stone.
"*": These cells are flooded.

At each second, you can move to a cell that shares a side with your current cell (if it exists). Also, at each second, every empty cell that shares a side with a flooded cell becomes flooded as well.
There are two problems ahead of your journey:

You can’t step on stone cells.
You can’t step on flooded cells since you will drown (also, you can’t step on a cell that will be flooded at the same time as you step on it).

Return _theminimum time it takes you to reach the destination in seconds, or _-1 if it is impossible.

Note that the destination will never be flooded.

Examples

Example 1:

1
2
3
4
5
6


Input: land = [["D",".","*"],[".",".","."],[".","S","."]]
Output: 3
Explanation: The picture below shows the simulation of the land second by second. The blue cells are flooded, and the gray cells are stone.
Picture (0) shows the initial state and picture (3) shows the final state when we reach destination. As you see, it takes us 3 second to reach destination and the answer would be 3.
It can be shown that 3 is the minimum time needed to reach from S to D.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2800-2899/2814.Minimum%20Time%20Takes%20to%20Reach%20Destination%20Without%20Drowning/images/ex1.png)

Example 2:

1
2
3
4
5
6


Input: land = [["D","X","*"],[".",".","."],[".",".","S"]]
Output: -1
Explanation: The picture below shows the simulation of the land second by second. The blue cells are flooded, and the gray cells are stone.
Picture (0) shows the initial state. As you see, no matter which paths we choose, we will drown at the 3rd second. Also the minimum path takes us 4 seconds to reach from S to D.
So the answer would be -1.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2800-2899/2814.Minimum%20Time%20Takes%20to%20Reach%20Destination%20Without%20Drowning/images/ex2-2.png)

Example 3:

1
2
3


Input: land = [["D",".",".",".","*","."],[".","X",".","X",".","."],[".",".",".",".","S","."]]
Output: 6
Explanation: It can be shown that we can reach destination in 6 seconds. Also it can be shown that 6 is the minimum seconds one need to reach from S to D.

Constraints:

2 <= n, m <= 100
land consists only of "S", "D", ".", "*" and "X".
Exactly one of the cells is equal to "S".
Exactly one of the cells is equal to "D".

Solution

Method 1 – BFS with Flood Simulation

Intuition

We need to reach the destination before the flood blocks the path. By precomputing the time each cell gets flooded (using BFS from all flood sources), we can then use another BFS to find the shortest path from S to D, only stepping into cells before they flood.

Approach

Use BFS to compute the earliest time each cell becomes flooded.
Use BFS from S to D, only moving to cells that are not stone and not flooded at the current or next time.
Track visited cells with the time to avoid revisiting with worse timing.
Return the minimum time to reach D, or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <queue>
class Solution {
public:
    int minTimeToDestination(vector<vector<char>>& land) {
        int n = land.size(), m = land[0].size();
        vector<vector<int>> flood(n, vector<int>(m, INT_MAX));
        queue<pair<int,int>> q;
        int sx, sy, dx, dy;
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
            if (land[i][j] == '*') { flood[i][j] = 0; q.push({i,j}); }
            if (land[i][j] == 'S') { sx = i; sy = j; }
            if (land[i][j] == 'D') { dx = i; dy = j; }
        }
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        // Flood BFS
        while (!q.empty()) {
            auto [x,y] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x+d[0], ny = y+d[1];
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[x][y]+1) {
                    flood[nx][ny]=flood[x][y]+1; q.push({nx,ny});
                }
            }
        }
        // BFS from S
        queue<tuple<int,int,int>> q2; q2.push({sx,sy,0});
        vector<vector<int>> vis(n, vector<int>(m, INT_MAX)); vis[sx][sy]=0;
        while (!q2.empty()) {
            auto [x,y,t]=q2.front(); q2.pop();
            if (x==dx&&y==dy) return t;
            for (auto& d : dirs) {
                int nx=x+d[0], ny=y+d[1], nt=t+1;
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]!='X'&&nt<flood[nx][ny]&&nt<vis[nx][ny]) {
                    vis[nx][ny]=nt; q2.push({nx,ny,nt});
                }
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func minTimeToDestination(land [][]byte) int {
    n, m := len(land), len(land[0])
    flood := make([][]int, n)
    for i := range flood { flood[i] = make([]int, m); for j := range flood[i] { flood[i][j]=1<<30 } }
    var sx, sy, dx, dy int
    q := [][2]int{}
    for i := 0; i < n; i++ { for j := 0; j < m; j++ {
        if land[i][j]=='*' { flood[i][j]=0; q=append(q,[2]int{i,j}) }
        if land[i][j]=='S' { sx=i; sy=j }
        if land[i][j]=='D' { dx=i; dy=j }
    }}
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    for h:=0; h<len(q); h++ {
        x,y := q[h][0],q[h][1]
        for _,d := range dirs {
            nx,ny := x+d[0],y+d[1]
            if nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[x][y]+1 {
                flood[nx][ny]=flood[x][y]+1; q=append(q,[2]int{nx,ny})
            }
        }
    }
    vis := make([][]int, n)
    for i := range vis { vis[i]=make([]int,m); for j:=range vis[i]{vis[i][j]=1<<30} }
    q2 := [][3]int{{sx,sy,0}}
    vis[sx][sy]=0
    for h:=0; h<len(q2); h++ {
        x,y,t := q2[h][0],q2[h][1],q2[h][2]
        if x==dx&&y==dy { return t }
        for _,d := range dirs {
            nx,ny,nt := x+d[0],y+d[1],t+1
            if nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]!='X'&&nt<flood[nx][ny]&&nt<vis[nx][ny] {
                vis[nx][ny]=nt; q2=append(q2,[3]int{nx,ny,nt})
            }
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
    public int minTimeToDestination(char[][] land) {
        int n = land.length, m = land[0].length;
        int[][] flood = new int[n][m];
        for (int[] f : flood) Arrays.fill(f, Integer.MAX_VALUE);
        int sx=0,sy=0,dx=0,dy=0;
        Queue<int[]> q = new LinkedList<>();
        for (int i=0;i<n;i++) for (int j=0;j<m;j++) {
            if (land[i][j]=='*') { flood[i][j]=0; q.add(new int[]{i,j}); }
            if (land[i][j]=='S') { sx=i; sy=j; }
            if (land[i][j]=='D') { dx=i; dy=j; }
        }
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int nx=cur[0]+d[0], ny=cur[1]+d[1];
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[cur[0]][cur[1]]+1) {
                    flood[nx][ny]=flood[cur[0]][cur[1]]+1; q.add(new int[]{nx,ny});
                }
            }
        }
        int[][] vis = new int[n][m];
        for (int[] v : vis) Arrays.fill(v, Integer.MAX_VALUE);
        Queue<int[]> q2 = new LinkedList<>(); q2.add(new int[]{sx,sy,0}); vis[sx][sy]=0;
        while (!q2.isEmpty()) {
            int[] cur = q2.poll();
            int x=cur[0],y=cur[1],t=cur[2];
            if (x==dx&&y==dy) return t;
            for (int[] d : dirs) {
                int nx=x+d[0], ny=y+d[1], nt=t+1;
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]!='X'&&nt<flood[nx][ny]&&nt<vis[nx][ny]) {
                    vis[nx][ny]=nt; q2.add(new int[]{nx,ny,nt});
                }
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
    fun minTimeToDestination(land: Array<CharArray>): Int {
        val n = land.size; val m = land[0].size
        val flood = Array(n) { IntArray(m) { Int.MAX_VALUE } }
        var sx=0; var sy=0; var dx=0; var dy=0
        val q = ArrayDeque<Pair<Int,Int>>()
        for (i in 0 until n) for (j in 0 until m) {
            when (land[i][j]) {
                '*' -> { flood[i][j]=0; q.add(i to j) }
                'S' -> { sx=i; sy=j }
                'D' -> { dx=i; dy=j }
            }
        }
        val dirs = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
        while (q.isNotEmpty()) {
            val (x,y) = q.removeFirst()
            for ((dx_,dy_) in dirs) {
                val nx=x+dx_; val ny=y+dy_
                if (nx in 0 until n && ny in 0 until m && land[nx][ny]=='.' && flood[nx][ny]>flood[x][y]+1) {
                    flood[nx][ny]=flood[x][y]+1; q.add(nx to ny)
                }
            }
        }
        val vis = Array(n) { IntArray(m) { Int.MAX_VALUE } }
        val q2 = ArrayDeque<Triple<Int,Int,Int>>()
        q2.add(Triple(sx,sy,0)); vis[sx][sy]=0
        while (q2.isNotEmpty()) {
            val (x,y,t) = q2.removeFirst()
            if (x==dx && y==dy) return t
            for ((dx_,dy_) in dirs) {
                val nx=x+dx_; val ny=y+dy_; val nt=t+1
                if (nx in 0 until n && ny in 0 until m && land[nx][ny]!='X' && nt<flood[nx][ny] && nt<vis[nx][ny]) {
                    vis[nx][ny]=nt; q2.add(Triple(nx,ny,nt))
                }
            }
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from collections import deque
class Solution:
    def minTimeToDestination(self, land: list[list[str]]) -> int:
        n, m = len(land), len(land[0])
        flood = [[float('inf')]*m for _ in range(n)]
        sx=sy=dx=dy=0
        q = deque()
        for i in range(n):
            for j in range(m):
                if land[i][j]=='*': flood[i][j]=0; q.append((i,j))
                if land[i][j]=='S': sx,sy=i,j
                if land[i][j]=='D': dx,dy=i,j
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        while q:
            x,y = q.popleft()
            for dx_,dy_ in dirs:
                nx,ny = x+dx_,y+dy_
                if 0<=nx<n and 0<=ny<m and land[nx][ny]=='.' and flood[nx][ny]>flood[x][y]+1:
                    flood[nx][ny]=flood[x][y]+1; q.append((nx,ny))
        vis = [[float('inf')]*m for _ in range(n)]
        q2 = deque([(sx,sy,0)])
        vis[sx][sy]=0
        while q2:
            x,y,t = q2.popleft()
            if x==dx and y==dy: return t
            for dx_,dy_ in dirs:
                nx,ny,nt = x+dx_,y+dy_,t+1
                if 0<=nx<n and 0<=ny<m and land[nx][ny]!='X' and nt<flood[nx][ny] and nt<vis[nx][ny]:
                    vis[nx][ny]=nt; q2.append((nx,ny,nt))
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


use std::collections::VecDeque;
impl Solution {
    pub fn min_time_to_destination(land: Vec<Vec<char>>) -> i32 {
        let n = land.len(); let m = land[0].len();
        let mut flood = vec![vec![i32::MAX; m]; n];
        let (mut sx, mut sy, mut dx, mut dy) = (0,0,0,0);
        let mut q = VecDeque::new();
        for i in 0..n { for j in 0..m {
            if land[i][j]=='*' { flood[i][j]=0; q.push_back((i,j)); }
            if land[i][j]=='S' { sx=i; sy=j; }
            if land[i][j]=='D' { dx=i; dy=j; }
        }}
        let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
        while let Some((x,y)) = q.pop_front() {
            for (dx_,dy_) in dirs.iter() {
                let nx = x as i32 + dx_; let ny = y as i32 + dy_;
                if nx>=0 && nx<n as i32 && ny>=0 && ny<m as i32 && land[nx as usize][ny as usize]=='.' && flood[nx as usize][ny as usize]>flood[x][y]+1 {
                    flood[nx as usize][ny as usize]=flood[x][y]+1; q.push_back((nx as usize,ny as usize));
                }
            }
        }
        let mut vis = vec![vec![i32::MAX; m]; n];
        let mut q2 = VecDeque::new(); q2.push_back((sx,sy,0)); vis[sx][sy]=0;
        while let Some((x,y,t)) = q2.pop_front() {
            if x==dx && y==dy { return t }
            for (dx_,dy_) in dirs.iter() {
                let nx = x as i32 + dx_; let ny = y as i32 + dy_; let nt = t+1;
                if nx>=0 && nx<n as i32 && ny>=0 && ny<m as i32 && land[nx as usize][ny as usize]!='X' && nt<flood[nx as usize][ny as usize] && nt<vis[nx as usize][ny as usize] {
                    vis[nx as usize][ny as usize]=nt; q2.push_back((nx as usize,ny as usize,nt));
                }
            }
        }
        -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    minTimeToDestination(land: string[][]): number {
        const n = land.length, m = land[0].length;
        const flood = Array.from({length:n},()=>Array(m).fill(Infinity));
        let sx=0,sy=0,dx=0,dy=0;
        const q: [number,number][] = [];
        for (let i=0;i<n;i++) for (let j=0;j<m;j++) {
            if (land[i][j]=='*') { flood[i][j]=0; q.push([i,j]); }
            if (land[i][j]=='S') { sx=i; sy=j; }
            if (land[i][j]=='D') { dx=i; dy=j; }
        }
        const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
        for (let h=0;h<q.length;h++) {
            const [x,y]=q[h];
            for (const [dx_,dy_] of dirs) {
                const nx=x+dx_,ny=y+dy_;
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[x][y]+1) {
                    flood[nx][ny]=flood[x][y]+1; q.push([nx,ny]);
                }
            }
        }
        const vis = Array.from({length:n},()=>Array(m).fill(Infinity));
        const q2: [number,number,number][] = [[sx,sy,0]];
        vis[sx][sy]=0;
        for (let h=0;h<q2.length;h++) {
            const [x,y,t]=q2[h];
            if (x==dx&&y==dy) return t;
            for (const [dx_,dy_] of dirs) {
                const nx=x+dx_,ny=y+dy_,nt=t+1;
                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]!='X'&&nt<flood[nx][ny]&&nt<vis[nx][ny]) {
                    vis[nx][ny]=nt; q2.push([nx,ny,nt]);
                }
            }
        }
        return -1;
    }
}

Complexity

⏰ Time complexity: O(n*m) — Each cell is visited at most once in both BFS passes.
🧺 Space complexity: O(n*m) — For flood and visited arrays.

Problem#

Examples#

Solution#

Method 1 – BFS with Flood Simulation#

Intuition#

Approach#

Code#

Complexity#