#1368
Minimum Cost to Make at Least One Valid Path in a Grid
specialist · 975 · lc hard +32 · verified · 70.9% accepted · 2,593 likes · top 80%
Description
In an m x n grid, each cell holds a directional sign: 1 (right), 2 (left), 3 (down), or 4 (up). Starting at (0, 0), a valid path follows these signs to arrive at (m - 1, n - 1). You may change any cell's sign for a cost of 1 (each cell at most once). Return the minimum cost to ensure at least one valid path from the top-left to 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
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.
Example 2:
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).
Example 3:
Input: grid = [[1,2],[4,3]]
Output: 1
Code
1
2
3