Minimum time to visit a cell in a grid

Array Breadth-First Search Graph Theory Heap (Priority Queue) Matrix Shortest Path

56.3% acceptance

Feb 25, 2026

1131

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col]. You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second. Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let m = grid.len();
    let n = grid[0].len();

    // If both neighbors of (0,0) are > 1, we can't start moving
    if grid[0][1] > 1 && grid[1][0] > 1 {
      return -1;
    }

    let mut dist = vec![vec![i32::MAX; n]; m];
    dist[0][0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i32, 0usize, 0usize)));

    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];

    while let Some(Reverse((t, r, c))) = heap.pop() {
      if r == m - 1 && c == n - 1 { return t; }
      if t > dist[r][c] { continue; }
      for (dr, dc) in &dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 { continue; }
        let nr = nr as usize;
        let nc = nc as usize;
        let arrive = t + 1;
        let g = grid[nr][nc];
        let new_t = if arrive >= g {
          arrive
        } else {
          // Need to oscillate; parity adjustment
          g + (g - arrive) % 2
        };
        if new_t < dist[nr][nc] {
          dist[nr][nc] = new_t;
          heap.push(Reverse((new_t, nr, nc)));
        }
      }
    }
    -1
  }
}