DSA problem
Minimum Cost to Make at Least One Valid Path in a Grid
Given an m x n grid, each cell has a sign pointing in one of four directions: 1 = right, 2 = left, 3 = down, 4 = up. When you stand on a cell, you must follow the sign on it; if the sign points right you move to the cell on the right, and similarly for the other directions. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). The cost of modifying a sign on a cell is 1, and you can modify each sign at most once. Return the minimum cost to make at least one valid path from (0, 0) to (m - 1, n - 1).
Although categorised as an MST / shortest-path problem, this is really a shortest-path on a 0-1 weighted graph. Treat every cell as a node, with edges to its four neighbours: the edge in the direction the sign already points has weight 0 (it costs nothing to follow), and every other neighbour edge has weight 1 (you would need to flip the sign once to go that way). The answer is the shortest path from (0, 0) to (m - 1, n - 1) in this graph.
A standard Dijkstra would work, but with only two edge weights (0 and 1) there is a much faster technique: 0-1 BFS. Use a deque (double-ended queue). When you traverse a 0-weight edge, push the next node to the front of the deque; when you traverse a 1-weight edge, push it to the back. This preserves the BFS invariant that nodes are processed in nondecreasing order of distance, but in O(V + E) time instead of O((V + E) log V) — for an m x n grid that is O(m * n).
The connection to MST is conceptual: every "modification" you pay for is, in essence, an extra cost-1 edge being introduced into a graph whose original edges are free. The minimum number of modifications needed to reach the goal is the same kind of "minimum total weight" question that MSTs answer for full spanning trees.
Examples
grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]3grid = [[1,1,3],[3,2,2],[1,1,4]]0grid = [[1,2],[4,3]]1Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- 1 <= grid[i][j] <= 4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.