給出一個2D的grid，求從左上角到右下角的最短路（總路長定義為max（所有相鄰節(jié)點的差））
1 #1631
2 #Runtime: 673 ms (Beats 64.49%)
3 #Memory: 16.1 MB (Beats 32.71%)
4
5 class Solution(object):
6 def minimumEffortPath(self, heights):
7 """
8 :type heights: List[List[int]]
9 :rtype: int
10 """
11 hq = [(0, (0, 0))]
12 vis = {(0, 0) : 0}
13 d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
14 target = (len(heights) - 1, len(heights[0]) - 1)
15 while hq:
16 cst, node = heapq.heappop(hq)
17 if node == target:
18 break
19 x, y = node
20 for t in d:
21 tx, ty = x + t[0], y + t[1]
22 if 0 <= tx < len(heights) and 0 <= ty < len(heights[0]):
23 tp_cst = max(cst, abs(heights[x][y] - heights[tx][ty]))
24 if (tx, ty) not in vis or ((tx, ty) in vis and tp_cst < vis[(tx, ty)]):
25 vis[(tx, ty)] = tp_cst
26 heapq.heappush(hq, (tp_cst, (tx, ty)))
27 return vis[target]