Minimum time takes to reach destination without drowning

Array Breadth-First Search Matrix

54.6% acceptance

Mar 31, 2026

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 the minimum time it takes you to reach the destination in seconds, or -1 if it is impossible. Note that the destination will never be flooded.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_seconds(land: Vec<Vec<String>>) -> i32 {
    use std::collections::VecDeque;
    let n = land.len();
    let m = land[0].len();
    let mut flood_time = vec![vec![i32::MAX; m]; n];
    let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
    let (mut sr, mut sc) = (0, 0);
    let (mut dr, mut dc) = (0, 0);
    for i in 0..n {
      for j in 0..m {
        match land[i][j].as_str() {
          "*" => { flood_time[i][j] = 0; queue.push_back((i, j)); }
          "S" => { sr = i; sc = j; }
          "D" => { dr = i; dc = j; }
          _ => {}
        }
      }
    }
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    // BFS for flood times
    while let Some((r, c)) = queue.pop_front() {
      for &(dx, dy) in &dirs {
        let nr = r as i32 + dx;
        let nc = c as i32 + dy;
        if nr < 0 || nr >= n as i32 || nc < 0 || nc >= m as i32 { continue; }
        let (nr, nc) = (nr as usize, nc as usize);
        if land[nr][nc] == "X" || land[nr][nc] == "D" { continue; }
        let nt = flood_time[r][c] + 1;
        if nt < flood_time[nr][nc] {
          flood_time[nr][nc] = nt;
          queue.push_back((nr, nc));
        }
      }
    }
    // BFS from S
    let mut dist = vec![vec![i32::MAX; m]; n];
    dist[sr][sc] = 0;
    queue.push_back((sr, sc));
    while let Some((r, c)) = queue.pop_front() {
      let t = dist[r][c] + 1;
      for &(dx, dy) in &dirs {
        let nr = r as i32 + dx;
        let nc = c as i32 + dy;
        if nr < 0 || nr >= n as i32 || nc < 0 || nc >= m as i32 { continue; }
        let (nr, nc) = (nr as usize, nc as usize);
        if land[nr][nc] == "X" { continue; }
        if t >= dist[nr][nc] { continue; }
        if land[nr][nc] != "D" && t >= flood_time[nr][nc] { continue; }
        dist[nr][nc] = t;
        queue.push_back((nr, nc));
      }
    }
    if dist[dr][dc] == i32::MAX { -1 } else { dist[dr][dc] }
  }
}