Minimum Cost to Make at Least One Valid Path in a Grid

hard array bfs graph heap matrix shortest path

Problem

Each cell of an m x n grid has an arrow (1=right, 2=left, 3=down, 4=up). Move with the arrow for free; changing an arrow costs 1. Return the minimum cost to reach (m-1, n-1) from (0,0).

Inputgrid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

Output3

Flip three arrows at row boundaries.

grid (JSON)

from collections import deque
def min_cost(grid):
    m, n = len(grid), len(grid[0])
    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    d = [(0,1),(0,-1),(1,0),(-1,0)]  # 1,2,3,4
    while dq:
        r, c = dq.popleft()
        for k, (dr, dc) in enumerate(d, 1):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                cost = 0 if grid[r][c] == k else 1
                if dist[r][c] + cost < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + cost
                    if cost == 0: dq.appendleft((nr, nc))
                    else: dq.append((nr, nc))
    return dist[m-1][n-1]

function minCost(grid) {
  const m = grid.length, n = grid[0].length;
  const dist = Array.from({length: m}, () => new Array(n).fill(Infinity));
  dist[0][0] = 0;
  const dq = [[0, 0]];
  const d = [[0,1],[0,-1],[1,0],[-1,0]];
  while (dq.length) {
    const [r, c] = dq.shift();
    d.forEach(([dr, dc], i) => {
      const nr = r + dr, nc = c + dc, k = i + 1;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
        const cost = grid[r][c] === k ? 0 : 1;
        if (dist[r][c] + cost < dist[nr][nc]) {
          dist[nr][nc] = dist[r][c] + cost;
          if (cost === 0) dq.unshift([nr, nc]); else dq.push([nr, nc]);
        }
      }
    });
  }
  return dist[m-1][n-1];
}

class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        Deque dq = new ArrayDeque<>(); dq.offer(new int[]{0, 0});
        int[][] d = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!dq.isEmpty()) {
            int[] p = dq.poll();
            int r = p[0], c = p[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + d[k][0], nc = c + d[k][1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int cost = grid[r][c] == k + 1 ? 0 : 1;
                if (dist[r][c] + cost < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + cost;
                    if (cost == 0) dq.offerFirst(new int[]{nr, nc}); else dq.offer(new int[]{nr, nc});
                }
            }
        }
        return dist[m-1][n-1];
    }
}

int minCost(vector>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector> dist(m, vector(n, INT_MAX));
    dist[0][0] = 0;
    deque> dq; dq.push_back({0, 0});
    int dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0};
    while (!dq.empty()) {
        auto [r, c] = dq.front(); dq.pop_front();
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int cost = grid[r][c] == k + 1 ? 0 : 1;
            if (dist[r][c] + cost < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + cost;
                if (cost == 0) dq.push_front({nr, nc}); else dq.push_back({nr, nc});
            }
        }
    }
    return dist[m-1][n-1];
}

Explanation

Think of each cell as a node. Moving in the direction the arrow already points is free (cost 0), while moving any other direction means flipping an arrow, which costs 1. We want the cheapest path from the top-left to the bottom-right.

Since edge costs are only 0 or 1, we can use 0-1 BFS instead of a full Dijkstra. It uses a deque: a 0-cost move is pushed to the front, and a 1-cost move to the back. This keeps the deque in increasing-distance order, so the first time we pop a cell its distance is final.

We track dist for every cell. When we pop (r, c), we try all four directions; the cost is 0 if grid[r][c] matches that direction (k), else 1. We relax the neighbor and push it to the right end of the deque.

This is much faster than re-sorting a heap, while still finding the true shortest path.

Example: in a grid of all-right then all-left rows, you follow arrows for free across each row and only pay 1 to drop down at each row boundary, giving a total of 3.

Time: O(m·n) Space: O(m·n)