790. The Climb With the Gentlest Step
A survey map is a grid of R rows and C columns; cell (r, c) has height
h[r][c]. A walker starts at the top left cell and must reach the bottom right cell, stepping
only to a cell sharing a side with the current one.
The STRAIN of a route is the largest height difference between two cells taken one after the
other, that is the largest abs(h[next] - h[current]) over the whole route.
Print the smallest strain any route can achieve.
1 2 2 1 2 3
3 8 2 -> 2 3 8 4 -> 1
5 3 5 5 3 5
In the left map the route down the first column and along the bottom row meets steps of 2, 2 and 2, so its strain is 2. No route does better, because leaving the start cell costs at least 1 and every route must eventually reach the 5 in the corner.
## Why this is not a shortest path
The cost of a route here is the MAXIMUM of its steps, not their sum. Adding one more gentle step costs nothing at all, so a longer detour is often better than a short scramble. Every algorithm that adds edge costs, and every dynamic programme over the grid, is answering a different question.
## Why scanning the candidate strains one at a time is too slow
A candidate strain s is easy to test: keep only the moves whose height difference is at most
s, then ask whether the two corners are connected. That is one breadth first search, O(R * C).
The obvious program tries s = 0, then 1, then 2, stopping at the first that connects.
Heights reach 10^6, so there are a million candidates and at 200 * 200 cells each that is
4 * 10^10 cell visits.
## Why the predicate is monotone
Suppose a route has strain at most s. Every one of its steps has a difference of at most s,
therefore at most s + 1, therefore at most anything larger. The same route still works. So
connected(s) is true => connected(s2) is true for every s2 > s
The answers to "does strain s suffice?" read no no no YES YES YES, and the answer is the
first YES. Nothing about the grid is sorted; the ordering lives in the candidate values.
## The bounds
lo = 0, which is correct when every cell on some route has the same height.
hi = max(h) - min(h). At that strain no step is forbidden, so the whole grid is one region and
the corners are certainly connected. That is what guarantees the search returns a strain that
actually works.
## The boundary that breaks a careless implementation
A one by one grid. The start cell IS the target cell, the walker takes no step at all, and the answer is 0. A check written as "pop a cell, look at its neighbours, report success when a neighbour is the target" never reports success, because the target is never a neighbour of anything. Mark the start as reached and test the cell when it comes OUT of the queue.
## Related problems
Problem 1645 is this question on a general graph, where the threshold selects edges rather than moves. Problem 791 keeps the grid but puts the threshold on the CELL values instead of on the differences between them, and problem 792 flips the objective to maximise the smallest value a route touches.
## Cost
Time O(R * C * log(max h)). Space O(R * C).
Constraints - `1 ≤ R ≤ 200` - `1 ≤ C ≤ 200` - `0 ≤ h[r][c] ≤ 10^6`
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers, the heights of one row in order.
Output
Print one integer, the smallest strain a route from the top left cell to the bottom right cell can have. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.