Each entry grid[r][c] gives the earliest second at which you may enter that cell. Start at the top-left cell at time 0. Every second you must move one cell up, down, left, or right, staying inside the grid; you cannot remain in place. Entering a cell is allowed only if your arrival time is at least its value. You may revisit cells. Return the earliest time you can reach the bottom-right cell, or -1 if it is unreachable.
Example 1:
Input: grid = [[0,0],[0,0]]
Output: 2Explanation: Move right at time 1 and down at time 2. The destination is two moves from the start, so 2 is the earliest possible arrival.
Example 2:
Input: grid = [[0,1],[4,5]]
Output: 6Explanation: Move right at time 1, left at time 2, right at time 3, left at time 4, right at time 5, and down at time 6. The destination opens at time 5, but every route to it has an even number of moves, so arrival at time 5 is impossible.
Example 3:
Input: grid = [[0,2],[2,0]]
Output: -1Explanation: At time 1, both neighbors of the starting cell are still unavailable. You cannot wait in place, so there is no legal first move and the destination is unreachable.
Constraints:
- Each dimension is between
2and1000; all rows have equal length. - The total number of cells is at most
100000. 0 <= grid[r][c] <= 100000grid[0][0] == 0