759. Arrow Grid Repairs
A warehouse floor is a grid of conveyor tiles. In grid, each value tells where the tile pushes a parcel: 0 east (right), 1 south (down), 2 west (left) and 3 north (up). A parcel placed on the top-left tile is carried to the neighbouring tile the arrow points at; arrows that point off the floor do nothing useful.
You may rotate the arrow of any tile to any of the four directions, and each rotated tile costs one repair, no matter which direction it is turned to. Return the minimum number of tiles that must be rotated so that a parcel starting on the top-left tile can be carried, by following the arrows, to the bottom-right tile. The answer is 0 if the arrows already do it.
Example 1
- Input:
- grid = [[0,1],[3,2]]
- Output:
- 0
- Explanation:
From the top-left tile the arrow points east, then the top-right arrow points south onto the goal, so the existing arrows already lead there and the answer is 0.
Example 2
- Input:
- grid = [[2,2,2],[2,2,2],[2,2,2]]
- Output:
- 4
- Explanation:
Every arrow points west, so no tile helps going right or down; any route needs 4 moves and each of the 4 tiles it leaves must be rotated, giving 4.
Example 3
- Input:
- grid = [[1,0],[1,3]]
- Output:
- 1
- Explanation:
The start arrow already carries the parcel south, but the bottom-left arrow points south off the floor; rotating that one tile east delivers the parcel to the goal, so the answer is 1.
Constraints
- 1 ≤ grid.length, grid[0].length and grid.length * grid[0].length ≤ 106
- grid[i][j] is one of 0, 1, 2, 3
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m * n)
- Space
- O(m * n)