progress

~/problems / More shortest paths

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

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~35 min

Every cell of the m x n grid holds an arrow: 1 = right, 2 = left, 3 = down, 4 = up. Standing on a cell, you follow its arrow to the next cell. Arrows may point off the grid.

You may change the arrow of any cell, at a cost of 1 per cell (each cell is changed at most once). Write min_cost(grid) -> int returning the minimum total cost so that following arrows from the top-left cell reaches the bottom-right cell.

min_cost([[1, 1, 3],
          [2, 2, 3],
          [1, 1, 1]])   # 0  (right, right, down, down: the arrows already lead there)

min_cost([[2, 2],
          [2, 2]])      # 2  (change (0,0) to "down" and (1,0) to "right")
Left: the 3 by 3 grid of the first example drawn as arrows, already leading right, right, down, down to the bottom-right corner, cost 0. Right: the all-left 2 by 2 grid after changing (0, 0) to down and (1, 0) to right, which makes a path down then right, cost 2.

Constraints: 1 <= m, n <= 200; every grid value is in 1..4. Trying every set of changes is exponential. ⭐ Bonus: a speed test on a large grid earns a star at about O(m·n) (a log factor is fine).

Show hint

Instead of choosing which arrows to change, think of walking from cell to cell: stepping the way the current arrow points costs nothing, and stepping any other way costs one change. The answer is then the cheapest walk from the top-left to the bottom-right.

Topic: Bellman-Ford, Floyd-Warshall, 0-1 BFS. Negative edges, all-pairs, and deque BFS for 0/1 weights.

0:00
Ctrl ' run · Ctrl ↵ submit
esc