Swim in Rising Water
Hard · shortest path
A square lake bed is given as an n x n grid of numbers. The number in a cell is the height of the ground there. No two cells have the same height.
At time 0 the water level is 0, and it rises by exactly 1 every time step, so at time t the level is t everywhere. You may be in a cell only while its height is at most the water level, that is, only once the cell is under water. You may wait in a cell for as long as you like.
Swimming from a cell to a neighbour on its left, right, above or below takes no time, but both cells must be under water at that moment. You begin in the top-left cell as soon as it is under water.
Return the earliest time at which you can be standing in the bottom-right cell.
Examples
Example 1
Input: grid = [[0, 2], [1, 3]]
Output: 3
The bottom-right cell has height 3, so it only goes under water at time 3. At that moment the whole lake is under water.
Example 2
Input: grid = [[0, 1, 6], [2, 3, 5], [7, 8, 4]]
Output: 5
The route through heights 0, 1, 3, 5, 4 never needs the water above 5, and the end can only be entered from a cell of height 5 or 8.
Example 3
Input: grid = [[3, 0], [1, 2]]
Output: 3
You start on a cell of height 3, so you cannot even begin until time 3.
Constraints
- 1 <= n <= 50, where the grid has n rows and n columns.
- Every height is an integer from 0 to n * n - 1, and no two cells have the same height.