Minimum number of visited cells in a grid

Array Dynamic Programming Stack Breadth-First Search Union-Find Heap (Priority Queue) Matrix Monotonic Stack

23.6% acceptance

Feb 25, 2026

416

You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0). Starting from the cell (i, j), you can move to one of the following cells: Cells (i, k) with j < k <= grid[i][j] + j (rightward movement), or Cells (k, j) with i < k <= grid[i][j] + i (downward movement). Return the minimum number of cells you need to visit to reach the bottom-right cell (m - 1, n - 1). If there is no valid path, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_visited_cells(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    // BFS with sorted sets per row and column
    let mut row_sets: Vec<std::collections::BTreeSet<usize>> = (0..m)
      .map(|_| (0..n).collect())
      .collect();
    let mut col_sets: Vec<std::collections::BTreeSet<usize>> = (0..n)
      .map(|_| (0..m).collect())
      .collect();

    let mut dist = vec![vec![-1i32; n]; m];
    dist[0][0] = 1;
    row_sets[0].remove(&0);
    col_sets[0].remove(&0);

    let mut queue = std::collections::VecDeque::new();
    queue.push_back((0usize, 0usize));

    while let Some((r, c)) = queue.pop_front() {
      let d = dist[r][c];
      let jump = grid[r][c] as usize;

      // Move right in row r
      if jump > 0 {
        let col_max = (c + jump).min(n - 1);
        if col_max >= c + 1 {
          let cols: Vec<usize> = row_sets[r].range((c + 1)..=col_max).copied().collect();
          for nc in cols {
            row_sets[r].remove(&nc);
            col_sets[nc].remove(&r);
            dist[r][nc] = d + 1;
            if r == m - 1 && nc == n - 1 {
              return d + 1;
            }
            queue.push_back((r, nc));
          }
        }

        // Move down in col c
        let row_max = (r + jump).min(m - 1);
        if row_max >= r + 1 {
          let rows: Vec<usize> = col_sets[c].range((r + 1)..=row_max).copied().collect();
          for nr in rows {
            col_sets[c].remove(&nr);
            row_sets[nr].remove(&c);
            dist[nr][c] = d + 1;
            if nr == m - 1 && c == n - 1 {
              return d + 1;
            }
            queue.push_back((nr, c));
          }
        }
      }
    }

    dist[m - 1][n - 1]
  }
}