Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个2D的grid,求从左上角到右下角的最短路(总路长定义为max(所有相邻节点的差))


 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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理