A hiker crosses an R-by-C grid of integer elevations, stepping one cell at a time up, down, left, or right, from the top-left cell (0,0) to the bottom-right cell (R-1,C-1).
The strain of a route is the maximum, over all consecutive steps on the route, of the absolute difference in elevation between the two cells of that step. The hiker wants a route of minimum possible strain.
Report that minimum strain. (A single-cell grid has strain 0.)
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, the elevations.
A single integer: the minimum possible strain over all routes from start to end.
Example 1
Input
3 3 1 2 2 3 8 2 5 3 5
Expected
2
Explanation
The route 1-3-5-3-5 down the left side and along the bottom keeps every step within 2, which is the minimum achievable strain.
Example 2
Input
1 3 1 5 9
Expected
4
Explanation
The only route is 1-5-9 with step differences 4 and 4, so the strain is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →