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

Hard

Each cell of the grid holds a sign pointing to the next cell you move to: 1 = right, 2 = left, 3 = down, 4 = up. Starting at the top-left cell, you follow signs for free, but you may change the sign of any cell (cost 1 each). Return the minimum total cost to reach the bottom-right cell.

Example 1

Input:  grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3

Example 2

Input:  grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0

Example 3

Input:  grid = [[1,2],[4,3]]
Output: 1

Constraints

• 1 <= m, n <= 100
• 1 <= grid[i][j] <= 4.