Minimum Re-Wiring To Make A Valid Path
A grid of one-way connectors each points in a fixed direction (right, left, down, up). Following arrows is free; rotating a cell to point elsewhere costs 1. Find the minimum total cost to create a directed path from the top-left to the bottom-right cell.
Problem
Given an m x n grid where grid[i][j] is 1 (right), 2 (left), 3 (down), or 4 (up), return the minimum number of cells you must change so there is a valid directed path from (0,0) to (m-1,n-1). Moving along a cell's own arrow costs 0; entering any other direction costs 1.
Input
An m x n integer grid with values in {1,2,3,4}.
Output
The minimum cost (number of cell modifications).
Constraints
- 1 ≤ m, n ≤ 100
- grid[i][j] ∈ {1,2,3,4}
Examples
Example 1
Input
[[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output
3
Three direction changes route a path from top-left to bottom-right.
Example 2
Input
[[1,1,3],[3,2,2],[1,1,4]]
Output
0
Existing arrows already form a valid path.