Find minimum time to reach last room i

Array Graph Theory Heap (Priority Queue) Matrix Shortest Path

55.5% acceptance

Feb 23, 2026

539

174

There is a dungeon with n x m rooms arranged as a grid. You are given a 2D array moveTime of size n x m, where moveTime[i][j] represents the minimum time in seconds after which the room opens and can be moved to. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second. Return the minimum time to reach the room (n - 1, m - 1). Two rooms are adjacent if they share a common wall, either horizontally or vertically.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn min_time_to_reach(move_time: Vec<Vec<i32>>) -> i32 {
    let n = move_time.len();
    let m = move_time[0].len();
    let mut dist = vec![vec![i64::MAX; m]; n];
    dist[0][0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, 0usize, 0usize)));
    
    while let Some(Reverse((d, r, c))) = heap.pop() {
      if d > dist[r][c] { continue; }
      if r == n - 1 && c == m - 1 { return d as i32; }
      for (dr, dc) in [(-1i32,0),(1,0),(0,-1),(0,1)] {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= n as i32 || nc < 0 || nc >= m as i32 { continue; }
        let nr = nr as usize; let nc = nc as usize;
        let arrive = d.max(move_time[nr][nc] as i64) + 1;
        if arrive < dist[nr][nc] {
          dist[nr][nc] = arrive;
          heap.push(Reverse((arrive, nr, nc)));
        }
      }
    }
    dist[n-1][m-1] as i32
  }
}