Minimum Cost to Make at Least One Valid Path in a Grid — Hard Problem & Solution

Problem statement

Every cell of the m x n matrix grid holds a sign pointing to the next cell to visit:

• 1 — go right, to (i, j + 1);
• 2 — go left, to (i, j - 1);
• 3 — go down, to (i + 1, j);
• 4 — go up, to (i - 1, j).

Some signs may point outside the grid. Starting at (0, 0) and following the signs gives a path; it is valid if it reaches (m - 1, n - 1).

You may change the sign of any cell for a cost of 1 (each cell's sign at most once). Return the minimum total cost needed to make the grid contain at least one valid path.

Example 1

Input: grid = [[1,1,3],[2,2,3],[4,4,1]]
Output: 0
Explanation: Right, right, down, down already reaches the bottom-right corner.

Example 2

Input: grid = [[2,2],[2,2]]
Output: 2
Explanation: Every sign points left; at least two of them must be changed, e.g. `(0,0)` to right and `(0,1)` to down.

Example 3

Input: grid = [[1,4],[1,1]]
Output: 1

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• 1 <= grid[i][j] <= 4

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

Changing a sign is the same as taking a cost-1 edge out of that cell, so the task is a shortest path in a graph whose edges weigh 0 (follow the sign) or 1 (go elsewhere) — a 0-1 BFS.

Approach

1. Set dist[0][0] = 0 and all other distances to infinity; process cells in order of distance.
2. Pop the cell with the smallest distance d (a deque or two buckets — d and d + 1 — suffice). Skip it if already finalised.
3. For each of the four directions, the neighbour costs d if the cell's sign points there and d + 1 otherwise; relax it, pushing free moves into the current bucket and paid moves into the next.
4. Return dist[m-1][n-1] when the corner is finalised.

Why it works

A path that follows signs except at c cells costs exactly c, and changing a cell's sign twice never helps on a shortest path because a shortest path never revisits a cell. So the minimum cost equals the shortest-path distance with 0/1 weights, and 0-1 BFS is Dijkstra specialised to those weights — cells leave the buckets in non-decreasing distance order.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• A plain BFS that counts edges ignores the free moves; the weights matter.
• Free moves must be processed before paid ones of the same layer — push them to the front of the deque (or into the current bucket).
• A 1 × 1 grid costs 0 whatever its sign.

Reference solution

Python

from typing import List
from collections import deque

def minCost(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    moves = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        d = dist[r][c]
        for sign, (dr, dc) in moves.items():
            a, b = r + dr, c + dc
            if 0 <= a < m and 0 <= b < n:
                w = 0 if grid[r][c] == sign else 1
                if d + w < dist[a][b]:
                    dist[a][b] = d + w
                    if w == 0:
                        dq.appendleft((a, b))
                    else:
                        dq.append((a, b))
    return dist[m - 1][n - 1]

JavaScript

var minCost = function(grid) {
    var m = grid.length, n = grid[0].length, total = m * n;
    var DR = [0, 0, 0, 1, -1], DC = [0, 1, -1, 0, 0];
    var dist = new Array(total).fill(Infinity), done = new Array(total).fill(false);
    dist[0] = 0;
    var cur = [0];
    for (var level = 0; cur.length > 0; level++) {
        var next = [];
        while (cur.length > 0) {
            var u = cur.pop();
            if (done[u]) continue;
            done[u] = true;
            if (u === total - 1) return level;
            var r = Math.floor(u / n), c = u % n;
            for (var d = 1; d <= 4; d++) {
                var a = r + DR[d], b = c + DC[d];
                if (a < 0 || b < 0 || a >= m || b >= n) continue;
                var v = a * n + b, w = grid[r][c] === d ? 0 : 1;
                if (level + w < dist[v]) {
                    dist[v] = level + w;
                    if (w === 0) cur.push(v); else next.push(v);
                }
            }
        }
        cur = next;
    }
    return dist[total - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More matrix problems

• Zuma Game Hard
• Shortest Path in a Grid with Obstacles Elimination Hard
• Minimum Moves to Reach Target with Rotations Hard
• Shortest Path to Get All Keys Hard
• Shortest Cycle in a Graph Hard
• Divide Nodes Into the Maximum Number of Groups Hard