791. The Level the Water Has to Reach
A flooded quarry is a grid of R rows and C columns; the floor of cell (r, c) sits at
depth d[r][c]. When the water level is T, a cell is swimmable exactly when d[r][c] <= T.
A swimmer starts at the top left cell and wants to reach the bottom right cell, moving only between cells that share a side, and only through swimmable cells. Both corners count: the swimmer cannot start in a cell that is still dry.
Print the smallest level T at which the crossing is possible.
0 2 0 1 2 3 4
1 3 -> 3 24 23 22 21 5
12 13 14 15 16 -> 16
11 17 18 19 20
10 9 8 7 6
In the two by two quarry the swimmer must pass through the cell of depth 3, so the water has to reach 3. At level 2 the corner cell is still dry.
## What this problem is NOT
Problem 790 also searches a grid for a threshold, but there the threshold limits the DIFFERENCE between two cells taken one after the other. Here it limits the VALUE of each cell on its own. Change the whole grid by adding a thousand to every depth and problem 790's answer does not move at all, while this one's rises by exactly a thousand.
## Why scanning the levels one at a time is too slow
A level T is easy to test: keep the cells with d <= T and ask whether the corners are
connected. That is one breadth first search. But depths reach 10^9, so trying every level from
0 upward is 10^9 searches.
Sorting the distinct depths and walking them in order is better, and it is still R * C searches
where one is enough per halving.
## Why the predicate is monotone
Raising the level never removes a swimmable cell: d <= T implies d <= T2 whenever
T2 >= T. The swimmable region therefore only grows, and a route that existed at T still
exists at T2. Feasible levels form a suffix of the candidates, and binary search finds where
that suffix begins.
## The bounds
lo = max(d[0][0], d[R-1][C-1]). Below that one of the two corners is dry, so no level under it
can work, and starting there saves a needless slice of the range.
hi = max(d). At that level every cell is swimmable and the grid is one region.
## The boundary that breaks a careless implementation
Starting lo at 0 and forgetting to test the START cell. A check that begins by pushing the top
left cell into the queue without asking whether it is swimmable will report success at levels
where the swimmer is standing on dry rock. The two by two example above answers 3, not 1, for
exactly that reason.
The one by one grid is the second boundary: the answer is the depth of that single cell.
## Width
Depths reach 10^9. That still fits in a signed 32-bit integer, and nothing in this problem
adds or multiplies two depths together, so no wider type is needed anywhere. Checking that
rather than assuming it is the habit: the same grid with SUMS along the route would reach
4 * 10^13 and would need 64 bits.
## Related problems
Problem 790 is the same grid with the threshold on step differences. Problem 792 asks the mirror question, maximising the smallest value a route touches instead of minimising the largest.
## Cost
Time O(R * C * log(max d)). Space O(R * C).
Constraints - `1 ≤ R ≤ 200` - `1 ≤ C ≤ 200` - `0 ≤ d[r][c] ≤ 10^9`
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers, the depths of one row in order.
Output
Print one integer, the smallest water level at which the top left cell and the bottom right cell are joined by swimmable cells. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.