1069. Minimum Cost to Make at Least One Valid Path

Given an m x n grid where each cell has a sign 1 (right), 2 (left), 3 (down), or 4 (up) indicating the direction you follow for free, you may change the sign of any cell at cost 1. Return the minimum total cost to make a valid path from the top-left cell to the bottom-right cell. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum cost.

Examples

Input: {"grid":[[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]}
Output: 3
Explanation: Three sign changes are needed.

Input: {"grid":[[1,2],[4,3]]}
Output: 1
Explanation: One change makes a valid path.

Input: {"grid":[[1]]}
Output: 0
Explanation: Start equals end.

Constraints

• 1<=rows,cols<=100

Asked by