Swim in Rising Water

Problem

You are given an n x n grid of distinct integers grid[r][c] in the range 0..n²-1, where each value is the elevation of that cell. Water is rising: at time t every cell with elevation at most t is submerged. You can move between two side-adjacent cells only when both are submerged, and moving takes no time.

Starting from the top-left cell at time 0, what is the earliest time t at which you can reach the bottom-right cell?

• The grid is square, up to about 50 cells on a side.
• All elevations are distinct and use every value from 0 up to one less than the cell count exactly once.

Examples

• grid = [[1,3],[2,0]] → 2. Going down first crosses elevation 2, then the destination is already at 0; going right first would force crossing elevation 3, which is worse.
• grid = [[4,3,2,1,0],[5,23,22,21,6],[16,17,18,19,7],[15,24,25,20,8],[14,13,12,11,9]] → 9. A route along the top row and down the right edge never needs a cell above 9, while cutting through the middle forces a much higher cell.
• grid = [[9]] → 9. Single cell: you are already there, but only once it is submerged.

Hints

1. The time you need for a given path is determined by one cell on it. Which one?
2. Given a candidate time t, can you check quickly whether the destination is reachable using only cells with elevation <= t? What does that let you do with t?
3. Either binary search on t with a BFS/DFS check, or run Dijkstra where the "distance" of a path is the maximum elevation seen so far (minimax path).