Find minimum time to reach last room ii

Array Graph Theory Heap (Priority Queue) Matrix Shortest Path

67.9% acceptance

Feb 23, 2026

356

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 when you can start moving to that room. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes one second for one move and two seconds for the next, alternating between the two. 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();
    // parity: (r+c)%2 determines step cost: if (r+c) is even -> cost 1; if odd -> cost 2
    // dist[r][c] = min time to reach (r,c)
    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;
        // step cost: if (r+c) is even, cost is 1; else 2
        let step = if (r + c) % 2 == 0 { 1i64 } else { 2i64 };
        let arrive = d.max(move_time[nr][nc] as i64) + step;
        if arrive < dist[nr][nc] {
          dist[nr][nc] = arrive;
          heap.push(Reverse((arrive, nr, nc)));
        }
      }
    }
    dist[n-1][m-1] as i32
  }
}