A valley is mapped as a grid: elevation[r][c] is the ground height of cell (r, c). Rain starts at time 0 and the water level at time t is exactly t. You can stand in a cell only once the water there is at least as high as the ground, that is when t >= elevation[r][c], and at that point you can wade instantly to any up/down/left/right neighbour that is also flooded.
You start in the top-left cell and may wait as long as you like. Write earliest_crossing(elevation) -> int returning the earliest time at which you can be standing in the bottom-right cell.
earliest_crossing([[0, 2],
[1, 3]]) # 3 (you can't stand in the target cell before time 3)
earliest_crossing([[0, 1, 2, 3, 4],
[24, 23, 22, 21, 5],
[12, 13, 14, 15, 16],
[11, 17, 18, 19, 20],
[10, 9, 8, 7, 6]]) # 16 (the best route never climbs above 16)
earliest_crossing([[7]]) # 7
earliest_crossing([[3, 9, 1]]) # 9
1 <= rows, cols <= 250;0 <= elevation[r][c] <= 10^9. Heights may repeat.- Trying each water level in turn and checking reachability from scratch is far too slow at this size. Aim for O(N log N) where
N = rows · cols.
Show hint
the time needed to reach a cell along a route is the highest ground on that route. Grow the set of reachable cells from the start, always extending into the cell that can be reached the soonest.