Minimum Cost to Make a Valid Path in a Grid

Given a directional grid, return the minimum number of direction changes needed to create a valid route from the start cell to the target cell. Pattern focus: Weighted shortest path. This is a compact 0-1 cost graph where every move either costs 0 or 1.

Input Format

grid = direction grid

Output Format

minimum number of changes needed

Constraints

  • 1 <= rows, cols <= 100
  • Cells contain directions 1..4.

Examples

Example 1:

Input:

grid = [[1,1,3],[3,2,2],[1,1,4]]

Output:

0

Explanation:

The given directions already form a valid path.

Example 2:

Input:

grid = [[1,2],[4,3]]

Output:

1

Explanation:

One change is enough to connect start and end.

Example 3:

Input:

grid = [[2,2,2],[2,2,2]]

Output:

2

Explanation:

Multiple direction changes are necessary.

Loading...
Minimum Cost to Make a Valid Path in a Grid