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

Given a grid where each cell contains a direction, return the minimum number of direction changes needed to create a valid path from the top-left cell to the bottom-right cell. Pattern focus: Weighted shortest path. This is a classic 0-1 weighted graph problem that can be solved with deque-based shortest path logic or Dijkstra.

Input Format

grid = direction grid

Output Format

minimum number of direction changes needed

Constraints

  • 1 <= rows, cols <= 100
  • Each cell is one of 1, 2, 3, 4 representing directions.

Examples

Example 1:

Input:

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

Output:

0

Explanation:

The grid already contains a valid path.

Example 2:

Input:

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

Output:

1

Explanation:

One direction change is enough to connect start and end.

Example 3:

Input:

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

Output:

2

Explanation:

Some cells must be redirected to form a valid route.

Loading...
Minimum Cost to Make at Least One Valid Path…