PreviousNext
Coding/Graphs and trees

Minimum cost grid path

Write codeHard35 min

Your task

Each cell of an m x n grid contains an arrow (1=right, 2=left, 3=down, 4=up) giving the default outgoing direction. Starting at the top-left cell you follow arrows for free, but you may change the sign of any single cell once for a cost of 1 (then it keeps that new sign). Return the minimum total cost of modifications needed so that there exists a valid path from the top-left cell to the bottom-right cell.

Examples

min_cost_grid_path(grid: list[list[int]]) -> int
Example 1
Inputmin_cost_grid_path([[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]])
Output3