Each entry in grid is a direction: 1 means right, 2 left, 3 down, and 4 up. Start in the top-left cell and follow directions to reach the bottom-right cell without leaving the grid. You may change a cell's direction once, paying 1 for each changed cell. Return the minimum total cost needed to create such a path. The path may take more steps than a shortest geometric route. Directions may initially point outside the grid, and the destination's direction does not matter once you arrive.
Hatched cells show a minimum-cost path; arrows show the original directions.
Example 1:
Input: grid = [[4]]
Output: 0Explanation: The starting cell is also the destination. No direction needs to be changed, even though its arrow points outside the grid.
Example 2:
Input: grid = [[1,3],[1,4]]
Output: 0Explanation: Follow the top-left arrow right, then the top-right arrow down. This reaches the destination without changes; its upward arrow does not need to be followed.
Example 3:
Input: grid = [[2,2,2]]
Output: 2Explanation: The only route moves right twice. Change the first two arrows from left to right, costing 2. The last arrow can remain unchanged.
Constraints:
1 <= grid.length <= 100- Every row has the same length, between
1and100. 1 <= grid[i][j] <= 4