797. Timed Cell Entry
A laboratory floor is an m x n grid of rooms. The number grid[r][c] is the earliest second at which room (r, c) unlocks; a visitor can step into it at any second that is at least that number. A courier starts in room (0, 0) at second 0 and every second must move to one of the four neighbouring rooms, so standing still is impossible; stepping back and forth between two unlocked rooms is allowed, and it is the only way to burn time.
Return the minimum second at which the courier can be in the bottom-right room (m - 1, n - 1), or -1 if it is impossible. The start room has grid[0][0] = 0.
Example 1
- Input:
- grid = [[0,1,4],[3,2,1]]
- Output:
- 3
- Explanation:
Enter (0,1) at time 1, then (1,1) at time 2 (its opening time is 2), then (1,2) at time 3, which is the corner.
Example 2
- Input:
- grid = [[0,4,0],[3,0,0]]
- Output:
- -1
- Explanation:
Both neighbours of the start open after time 1, so the guard cannot make a first move at all; the answer is -1.
Example 3
- Input:
- grid = [[0,1,5],[9,9,0]]
- Output:
- 7
- Explanation:
Entering (0,2) at second 2 is too early because it unlocks at 5. Time can only be burned in pairs by bouncing, and 2 and 5 have different parity, so the earliest entry is second 6 and the corner follows at second 7.
Constraints
- 2 ≤ m, n ≤ 1000
- 0 ≤ grid[r][c] ≤ 105
- grid[0][0] = 0
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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(m * n * log(m * n))
- Space
- O(m * n)