Minimum Cost to Make at Least One Valid Path in a Grid
Hard · Graphs · Array · Breadth-First Search · Graph · Heap (Priority Queue) · Matrix · Shortest Path
Problem
You are given an m x n grid in which every cell holds a sign telling you where to go next:
- 1: move right, to grid[i][j + 1]
- 2: move left, to grid[i][j - 1]
- 3: move down, to grid[i + 1][j]
- 4: move up, to grid[i - 1][j]
Some signs point off the grid. You start at the top-left cell (0, 0). A valid path follows the signs from there all the way to the bottom-right cell (m - 1, n - 1).
You may change the sign in any cell for a cost of 1, at most once per cell. Return the smallest total cost that makes at least one valid path exist.
Examples
Input: grid = [[1,1,1],[2,2,3],[4,4,1]] Output: 1
The signs lead right along the top row and off the grid. Changing the sign at (0, 2) to point down (cost 1) sends the path down to (1, 2), whose sign leads on to the corner.
Input: grid = [[1,3],[2,1]] Output: 0
Right, then down: the signs already reach the corner.
Input: grid = [[4]] Output: 0
You start on the destination.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 100
- 1 <= grid[i][j] <= 4
Approaches
- Relax every cell until nothing changes — time O((m · n)²) in the worst case, space O(m · n)
Follow-up
Why is changing a sign at most once never a limit? A cheapest path never visits a cell twice, so it never needs two different signs in one cell. The same 0-1 BFS solves any grid where each step costs 0 or 1, such as knocking down walls; see the use case "Fewest walls to knock down".
Related problems
Start free on Cariara · Coding problems · System design studio
