Show problems as
Classic problem #1368HardArrayBreadth-First SearchGraph TheoryHeap (Priority Queue)MatrixShortest Path0-1 BFSDijkstra's Algorithm

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

Real-world version: Cheapest Rewiring Of Conveyor Arrows
Tracked in this browser only
Read Minimum Cost to Make at Least One Valid Path in a Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_rewiring_cost(grid: list[list[int]]) -> int:
Java
public int minRewiringCost(int[][] grid)

More on the same topics