题目

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
示例 3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-minimum-effort
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.dijistra
bfs + 优先队列
题目可以转化为路径权值的最小值，也就是最短路径
利用广度搜索+优先队列
找到节点q能到达的点的（距离，横坐标, 纵坐标） 然后利用优先队列，从最短的路径开始遍历能到达的点，最后到达坐标为 (m - 1, n - 1)的点就是答案
这题与的路径长度定义为：一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
所以可以用dijistra
证明：dijisitra 属于 它是 A* 算法在启发函数 h≡0 时的特殊情况,具体证明自行百度。这一块本人也不太懂。

  1. class Solution:
  2.     def minimumEffortPath(self, heights: List[List[int]]) -> int:
  3.         m, n = len(heights), len(heights[0])
  4.         q = [(0, 0, 0)]
  5.         dist = [0] + [float("inf")] * (m * n - 1)
  6.         seen = set()
  8.         while q:
  9.             d, x, y = heapq.heappop(q)
  10.             iden = x * n + y
  11.             if iden in seen:
  12.                 continue
  13.             if (x, y) == (m - 1, n - 1):
  14.                 break
  16.             seen.add(iden)
  17.             for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
  18.                 if 0 <= nx < m and 0 <= ny < n and max(d, abs(heights[x][y] - heights[nx][ny])) <= dist[nx * n + ny]:
  19.                     dist[nx * n + ny] = max(d, abs(heights[x][y] - heights[nx][ny]))
  20.                     heapq.heappush(q, (dist[nx * n + ny], nx, ny))
  22.         return dist[m * n - 1]

2.二分答案
本题可以利用二分答案，先定义路径，再利用dfs寻找路径长度<=规定长度的路径，直到只能找到一条路径为止。
3.SPFA
也称为：队列优化的bellmen ford
据说：时间复杂度没有保证。
4.并查集