Swim in Rising Water
HardGraphs
You are given an n x n integer grid where grid[r][c] is the elevation of cell (r, c). Every value from 0 to n^2 - 1 appears exactly once.
It starts raining, and at time t the water level everywhere is t. You can swim from a cell to a neighbouring cell (up, down, left, or right) only if both cells have elevation at most t. Swimming takes no time, so at a given t you can cover any distance through cells that are under water. You cannot leave the grid.
You start in the top-left cell (0, 0). Return the smallest time t at which you can reach the bottom-right cell (n - 1, n - 1).
Equivalently: over all paths from the top-left to the bottom-right cell, find the path whose highest elevation is as small as possible, and return that highest elevation (the start and end cells count too).
Example 1
- Input:
- grid = [[0, 6, 7, 8], [1, 13, 14, 9], [2, 3, 12, 10], [4, 5, 11, 15]]
- Output:
- 15
- Explanation
- Going down the left column and along the bottom never climbs above 5 until the last cells:
0, 1, 2, 4, 5, 11, 15. Any route must finish on the corner cell, whose elevation is 15, so the answer is 15.
Example 2
- Input:
- grid = [[0, 7, 4], [8, 6, 3], [1, 2, 5]]
- Output:
- 7
- Explanation
- The start's only neighbours are 7 (right) and 8 (down), so you cannot leave before
t = 7. Att = 7the route0 -> 7 -> 4 -> 3 -> 5is entirely under water, so the answer is 7.
Example 3
- Input:
- grid = [[3, 0], [1, 2]]
- Output:
- 3
- Explanation
- You cannot even leave the start until the water reaches its elevation of 3. At
t = 3every cell is under water, so you can swim straight to the corner.
Constraints
n == grid.length == grid[i].length- 1 ≤
n≤ 50 - 0 ≤
grid[r][c]<n^2 - Every value in
gridis unique