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

Minimum Cost to Make at Least One Valid Path in a Grid looks like a plain shortest-path problem, but it has a twist that unlocks a beautiful trick: every move costs either 0 or 1. That single fact lets us drop the priority queue and use a plain deque instead — the 0-1 BFS pattern.

The slow way first

You could try Dijkstra with a min-heap: treat each cell as a node, give weight 0 to the edge that follows a cell's arrow and weight 1 to the three edges that fight it, then run shortest path. That is correct, but the heap costs an extra log factor on every push and pop — O(R·C·log(R·C)).

The question to ask: do I really need a heap? A heap exists to always serve the cheapest frontier node first. But here the only edge weights are 0 and 1. When weights are that simple, a humble deque can keep the frontier sorted for free.

The idea: a deque, front for free, back for paid

Walk the grid like BFS, but use a double-ended queue. When you expand a cell:

• The neighbor in the cell's own arrow direction costs 0 — push it on the front of the deque.
• The other three neighbors cost 1 — push them on the back.

Because cost-0 moves go to the front and cost-1 moves go to the back, the deque always holds cells in non-decreasing cost order. So popleft() always returns the cheapest unsettled cell, exactly like a heap would — but in O(1). The first time you pop a cell, its cost is final.

The key insight: with weights restricted to {0, 1}, front-loading the zeros keeps the deque ordered, so no priority queue is needed.

Walk through it

Step through the animation. A cell on the frontier is highlighted; a settled cell is dimmed as visited. Watch the deque label: free moves slide onto the front, paid moves wait at the back. Following the arrows → → ↓ ↓ runs straight from the start to the goal without ever turning, so the goal pops at cost 0 and the cost-1 cell at the back is never even needed.

Pseudocode

cost[start] = 0
deque = [start]
while deque is not empty:
    (r, c) = deque.popleft()          # cheapest cell first
    for each direction k and neighbor (nr, nc):
        if neighbor is inside the grid:
            w = 0 if grid[r][c] points toward k else 1
            nd = cost[(r, c)] + w
            if nd < best known cost of (nr, nc):
                cost[(nr, nc)] = nd
                if w == 0: deque.appendleft((nr, nc))   # free -> front
                else:      deque.append((nr, nc))       # paid -> back
return cost[goal]

The Python solution

def min_cost(grid):
    R, C = len(grid), len(grid[0])
    cost = {(0, 0): 0}
    dq = deque([(0, 0)])          # 0-1 BFS frontier
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while dq:
        r, c = dq.popleft()       # cheapest cell first
        for k, (dr, dc) in enumerate(dirs):
            nr, nc = r + dr, c + dc
            if in_grid(nr, nc):
                w = 0 if grid[r][c] == k + 1 else 1
                nd = cost[(r, c)] + w
                if nd < cost.get((nr, nc), inf):
                    cost[(nr, nc)] = nd
                    dq.appendleft((nr, nc)) if w == 0 else dq.append((nr, nc))
    return cost[(R - 1, C - 1)]

• dirs lists the four directions in the same order the sign values mean: index 0 = right (sign 1), 1 = left (sign 2), 2 = down (sign 3), 3 = up (sign 4).
• dq.popleft() (line 7) always returns the cheapest frontier cell, because zeros were front-loaded.
• w = 0 if grid[r][c] == k + 1 else 1 is the whole trick: following the arrow is free, any turn costs 1.
• nd < cost.get((nr, nc), inf) is the standard relaxation — we only push when we found a cheaper route.
• Line 15 is the 0-1 split: a free move jumps to the front (appendleft), a paid move goes to the back (append), which is what keeps the deque ordered.

Complexity

Restricting edge weights to {0, 1} lets the deque replace the heap, dropping the log factor. Every cell is settled once and each edge is relaxed a constant number of times, so the work is linear in the grid size.

When this pattern shows up

Practice