Cost d goes to the deque front; cost d+1 to its back. This maintains cheapest-first processing for weights restricted to zero and one.

Interpret every legal four-neighbor move as an edge: cost zero when it follows the current cell’s arrow, otherwise one. Store the best change count per cell and relax only improvements. The deque contains the current cost layer before the next one. Stale offers are skipped. Although the problem changes each arrow at most once, an optimal route can be chosen without cycles because removing a cycle never increases nonnegative cost. On that simple route every departing cell needs at most one change.

What the function promises: A rectangular nonempty grid uses 1=right, 2=left, 3=down, 4=up. Return the fewest arrow changes needed to connect the corners. Input is not mutated.

from collections import deque

def minimum_arrow_changes(grid):
    rows, cols = len(grid), len(grid[0])
    directions = ((0,1), (0,-1), (1,0), (-1,0))
    distance = [[float("inf")] * cols for _ in range(rows)]
    distance[0][0] = 0
    queue = deque([(0, 0, 0)])
    while queue:
        cost, r, c = queue.popleft()
        if cost != distance[r][c]:
            continue
        if (r, c) == (rows-1, cols-1):
            return cost
        for arrow, (dr, dc) in enumerate(directions, start=1):
            nr, nc = r+dr, c+dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            weight = int(grid[r][c] != arrow)
            candidate = cost + weight
            if candidate < distance[nr][nc]:
                distance[nr][nc] = candidate
                entry = (candidate, nr, nc)
                if weight == 0:
                    queue.appendleft(entry)
                else:
                    queue.append(entry)

assert minimum_arrow_changes([[1, 3], [1, 4]]) == 0
assert minimum_arrow_changes([[2, 2], [2, 2]]) == 2
assert minimum_arrow_changes([[4]]) == 0

Work and storage: O(V+E) time and O(V+E) space for 0–1 BFS; on a four-neighbor grid both reduce to O(RC). Equal-cost non-improving offers are not enqueued, so zero-cost cycles do not loop forever.

When to recognize it: Following an arrow costs 0. Choosing another direction costs 1. A deque can maintain this two-level frontier.

Check before applying it: Ordinary BFS minimizes moves, not arrow changes. Costs such as 2 or 7 need a different frontier, such as Dijkstra’s heap.

No. Preserve remaining change budget as part of the state, then use unit-move BFS. This is the same distinction developed in the obstacle-removal shortest-path lesson.