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")
Constraints: 1 <= m, n <= 200; every grid value is in 1..4. Trying every set of changes is exponential; aim for 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.