#225MediumGraphs· Dijkstra with a Minimax Cost

Least Effort Hiking Path

A hiking club has a height map of a nature reserve: `heights[r][c]` is the elevation in metres of the square at row `r`, column `c`. Hikers start in the top-left square and must reach the bottom-right square, moving one square at a time up, down, left or right. A hiker's **effort** on a route is not the total climbing, but the single hardest step: the largest absolute difference in elevation between two consecutive squares of the route. Return the smallest possible effort over all routes from the top-left to the bottom-right square.

Input format

`heights`: a rectangular grid of non-negative integers.

Output format

An integer: the minimum possible effort (0 for a single square).

Examples

Input: heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]

Output: 2

The route 1, 3, 5, 3, 5 (down, down, right, right) has steps 2, 2, 2, 2, so its effort is 2. Every route that avoids the 8 needs a step of at least 2, and routes through the 8 are worse.

Input: heights = [[1, 2, 3], [3, 8, 4], [5, 3, 5]]

Output: 1

The route 1, 2, 3, 4, 5 along the top row and down the right column changes by at most 1 per step.

Input: heights = [[7]]

Output: 0

Start and goal are the same square: effort 0.

Constraints

1 <= rows, columns <= 100
0 <= heights[r][c] <= 10^6

#dijkstra
#graph
#grid
#heap
#minimax