0763HardArrayBreadth-First SearchGraph TheoryHeap (Priority Queue)MatrixShortest Path0-1 BFSDijkstra's Algorithm

Cheapest Rewiring Of Conveyor Arrows

Tracked in this browser only

Trains the technique from

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

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A sorting floor is an m x n block of cells. Every cell carries one fixed arrow, and a tote sitting on a cell is pushed to the neighbouring cell that arrow points at. grid[r][c] gives the arrow code of the cell in row r, column c:

1 points right, to (r, c + 1);
2 points left, to (r, c - 1);
3 points down, to (r + 1, c);
4 points up, to (r - 1, c).

A tote is placed on (0, 0) and must end up on (m - 1, n - 1). It only ever moves the way the arrow under it points, and it may never be pushed off the edge of the floor.

Before releasing the tote you may rewire cells. Rewiring one cell sets its arrow to any of the four directions and costs 1, and no cell may be rewired more than once. Return the smallest total cost that leaves the tote able to travel from (0, 0) to (m - 1, n - 1). A tote already standing on (m - 1, n - 1) needs no moves and no rewiring.

Examples

Example 1

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

Rewire the cell at row 2, column 0 to point right. The tote then runs right along row 0, down into row 1, left along row 1, down into row 2, and from there right along row 2, down, left along row 3, down and right along row 4 onto (4, 4). One rewire is paid for.

Example 2

Input: grid = [[2], [2], [2]]
Output: 2

The floor is one column wide, so every arrow points off the edge. Rewiring row 0 and row 1 to point down carries the tote from (0, 0) to (2, 0) for a cost of 2.

Example 3

Input: grid = [[3, 3], [1, 1]]
Output: 0

The arrow on (0, 0) pushes the tote down to (1, 0), and the arrow there pushes it right onto (1, 1), so no cell needs rewiring.

Constraints

1 <= grid.length <= 100
1 <= grid[i].length <= 100
1 <= grid[i][j] <= 4
Every row of grid has the same length.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_rewiring_cost(grid: list[list[int]]) -> int:

Java

public int minRewiringCost(int[][] grid)

The intended approach

Time O(m n) for an m x n floor: each cell settles once and has four moves.Space O(m n) for the recorded costs and the layer lists.

Treat each cell as a node with four outgoing moves: the one matching its own arrow costs 0 and the other three cost 1. Because only two weights occur, shortest costs can be settled in layers: hold the set of cells reachable at the current cost, exhaust every free arrow out of them with a stack so the layer closes fully, and collect the cells reachable for one more into the next layer. Routes are free to run left and up, so a cell can be reopened when a cheaper arrival appears; the recorded cost of each cell is checked before it is expanded.

Pythonentry point: min_rewiring_cost

def min_rewiring_cost(grid):
    # 0-1 BFS held in cost layers: following a cell's own arrow is free, so the
    # whole free closure of a layer is exhausted with a stack before the layer of
    # cells that need one more rewire is opened.
    # Time O(m n), space O(m n).
    rows = len(grid)
    cols = len(grid[0])
    step = ((0, 1), (0, -1), (1, 0), (-1, 0))   # arrow codes 1, 2, 3, 4
    best = [[-1] * cols for _ in range(rows)]
    best[0][0] = 0
    layer = [(0, 0)]
    cost = 0
    while layer:
        stack = layer
        nxt = []
        while stack:
            r, c = stack.pop()
            if best[r][c] != cost:
                continue
            code = grid[r][c]
            for k in range(4):
                nr = r + step[k][0]
                nc = c + step[k][1]
                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue
                extra = 0 if k == code - 1 else 1
                nd = cost + extra
                if best[nr][nc] == -1 or nd < best[nr][nc]:
                    best[nr][nc] = nd
                    if extra == 0:
                        stack.append((nr, nc))
                    else:
                        nxt.append((nr, nc))
        cost += 1
        layer = nxt
    return best[rows - 1][cols - 1]

The obvious version

Repeated relaxation. Start every cell at a cost above any achievable value except the corner, then sweep the whole floor over and over, lowering a neighbour whenever a cheaper arrival is found, until a full sweep changes nothing. Costs up to m n sweeps of m n cells.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_rewiring_cost(grid):
    rows = len(grid)
    cols = len(grid[0])
    step = ((0, 1), (0, -1), (1, 0), (-1, 0))
    big = rows * cols + 5
    dist = [[big] * cols for _ in range(rows)]
    dist[0][0] = 0
    for _ in range(rows * cols + 1):
        changed = False
        for r in range(rows):
            for c in range(cols):
                here = dist[r][c]
                if here >= big:
                    continue
                code = grid[r][c]
                for k in range(4):
                    nr = r + step[k][0]
                    nc = c + step[k][1]
                    if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                        continue
                    nd = here + (0 if k == code - 1 else 1)
                    if nd < dist[nr][nc]:
                        dist[nr][nc] = nd
                        changed = True
        if not changed:
            break
    return dist[rows - 1][cols - 1]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in