Minimum Direction Changes for Grid Navigation (Hard) — Practice with Code Visualizer

You are given an m × n grid where each cell contains a directional indicator that suggests which adjacent cell to move to next. The directional values in grid[i][j] are encoded as follows:

1 → Move right (from grid[i][j] to grid[i][j+1])
2 → Move left (from grid[i][j] to grid[i][j-1])
3 → Move down (from grid[i][j] to grid[i+1][j])
4 → Move up (from grid[i][j] to grid[i-1][j])

Important: Some cells may have directional indicators pointing outside the grid boundaries.

Your objective is to navigate from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) by following a valid traversal path. You may override the direction of any cell at a cost of 1 per modification. Each cell's direction can only be modified at most once.

A valid path is any sequence of moves that successfully leads from the starting position to the destination, regardless of whether it is the shortest route.

Return the minimum total cost required to ensure at least one valid path exists from the origin to the destination.

Starting at (0,0), follow the arrows right to reach (0,3). Change direction to down (cost 1) to reach (1,3). Follow arrows left to (1,0). Change direction to down (cost 1) to reach (2,0). Follow arrows right to (2,3). Change direction to down (cost 1) to reach destination (3,3). Total cost = 3.

A valid path already exists without any modifications: (0,0) → (0,1) → (0,2) → (1,2) → (1,1) → (1,0) → (2,0) → (2,1) → (2,2). No changes needed, so the cost is 0.

From (0,0) the arrow points right to (0,1), but from there it points left back to (0,0). We need to change either (0,0) to point down or (0,1) to point down. After one modification, we can reach (1,1). Minimum cost = 1.