792. The Route That Keeps the Highest Floor
A cave floor is a grid of R rows and C columns; cell (r, c) has clearance v[r][c].
A crawler starts at the top left cell and must reach the bottom right cell, moving only between
cells that share a side.
The COMFORT of a route is the SMALLEST clearance among the cells it visits, both corners included. Print the largest comfort any route can achieve.
5 4 5
1 2 6 -> 4
7 4 6
The route 5 4 5 6 6 across the top and down the right side never drops below 4. Every other
route passes through a 1 or a 2.
## The mirror of problem 791, and why the difference matters
Problem 791 minimises the LARGEST value a route touches. This one maximises the SMALLEST. The machinery is the same and the two directions are not symmetric in code:
791: keep cells with v <= T, and we want T SMALL -> on success, hi = mid
792: keep cells with v >= T, and we want T LARGE -> on success, lo = mid
Getting the second one right is most of the exercise. A loop that halves with
mid = lo + (hi - lo) / 2 and then sets lo = mid on success never terminates when
hi = lo + 1, because mid comes out as lo and nothing changes. Round the midpoint UP
instead, mid = hi - (hi - lo) / 2, and pair it with hi = mid - 1 on failure.
## Why the predicate is monotone
If a route never drops below T, it never drops below anything smaller either, so the same
route proves the claim for every T2 <= T. The answers to "is comfort T reachable?" read
YES YES YES no no, and the answer is the LAST YES.
## The bounds
lo = 0, safe because clearances are never negative.
hi = min(v[0][0], v[R-1][C-1]). No route can beat the smaller of the two corners, because every
route visits both. Using max(v) also works and wastes a halving or two.
## The boundary that breaks a careless implementation
Two of them.
A one by one grid. The single cell is both corners, and the answer is its own clearance, which is
why hi is built from the corners rather than from an empty maximum.
A zero somewhere on the only route. The crawler must pass through it and the answer is 0, which
an implementation that treats 0 as "no answer" reports as -1.
## Width
Clearances reach 10^9, and they are only ever compared against the candidate, never added to
each other. A signed 32-bit integer holds every value here, so nothing overflows; the reason to
notice is that the very similar problem 803 adds ten thousand values of a million and does need
64 bits for its total.
## Related problems
Problem 791 is this grid with the objective and the comparison both flipped, and problem 1645 is the minimise version on a general graph.
## Cost
Time O(R * C * log(max v)). Space O(R * C).
Constraints - `1 ≤ R ≤ 200` - `1 ≤ C ≤ 200` - `0 ≤ v[r][c] ≤ 10^9`
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers, the clearances of one row in order.
Output
Print one integer, the largest possible smallest clearance on a route from the top left cell to the bottom right cell. 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.