Earliest Time to Reach the Far Corner
Each cell of a grid unlocks at a given second; you may enter a cell only at or after its unlock time. Moving to an adjacent cell takes one second, and you may pace back and forth to wait. Find the earliest arrival at the bottom-right.
Problem
Given an m x n matrix grid where grid[i][j] is the minimum time you may enter cell (i,j), you start at (0,0) at time 0 and move 4-directionally one cell per second. You may move back and forth between visited cells to pass time. Return the minimum time to reach (m-1,n-1), or -1 if it is impossible.
Input
An m x n integer matrix grid of entry times; grid[0][0] is 0.
Output
An integer: the earliest arrival time at the bottom-right, or -1.
Constraints
- 2 <= m, n <= 1000
- 0 <= grid[i][j] <= 10^5; grid[0][0] == 0.
Examples
Example 1
Input
grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output
7
Waiting where needed, the corner is reachable at time 7.
Example 2
Input
grid = [[0,2,4],[3,2,1],[1,0,4]]
Output
-1
Both cells adjacent to the start require time > 1, so you can never make a first move.