heights is a non-empty grid of integers. You start at the top-left cell and want to reach the bottom-right cell, moving up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it.
Write minimum_effort_path(heights) -> int returning the smallest possible effort.
minimum_effort_path([[1, 2, 2],
[3, 8, 2],
[5, 3, 5]]) # 2 (down the left column and along the bottom: 1, 3, 5, 3, 5)
minimum_effort_path([[4, 9, 4]]) # 5
minimum_effort_path([[7]]) # 0
Constraints: 1 <= rows, cols <= 200, 1 <= heights[r][c] <= 10**6. Trying every path is exponential; aim for about O(R·C·log(R·C)).
Show hint
treat cells as nodes and steps as edges weighted by the height difference. The usual shortest-path method still works when a route's cost is its largest edge instead of the sum of its edges.