Minimum cost to make at least one valid path in a grid

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

70.9% acceptance

Feb 25, 2026

2592

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be: 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1]) 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1]) 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j]) 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j]) Notice that there could be some signs on the cells of the grid that point outside the grid. You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest. You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only. Return the minimum cost to make the grid have at least one valid path.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::VecDeque;
    let m = grid.len();
    let n = grid[0].len();
    // Directions: 1=right, 2=left, 3=down, 4=up
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    let mut dist = vec![vec![i32::MAX; n]; m];
    dist[0][0] = 0;
    let mut deque: VecDeque<(usize,usize)> = VecDeque::new();
    deque.push_front((0,0));
    while let Some((r,c)) = deque.pop_front() {
      let d = dist[r][c];
      for (k, &(dr,dc)) in dirs.iter().enumerate() {
        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, nc) = (nr as usize, nc as usize);
        let cost = if grid[r][c] == (k+1) as i32 { 0 } else { 1 };
        let nd = d + cost;
        if nd < dist[nr][nc] {
          dist[nr][nc] = nd;
          if cost == 0 { deque.push_front((nr,nc)); } else { deque.push_back((nr,nc)); }
        }
      }
    }
    dist[m-1][n-1]
  }
}