重庆网站优化软件,权重2的网站,o2o商业模式,教务系统打卡记录 最小体力消耗路径
链接
Dijkstra
将Dijkstra算法从计算最短路径转化为计算路径最大差值。
class Solution:def minimumEffortPath(self, heights: List[List[int]]) - int:n, m len(heights), len(heights[0])dist [0] [0x3f3f3f3f] * (n * m - 1)vis set…打卡记录 最小体力消耗路径
链接
Dijkstra
将Dijkstra算法从计算最短路径转化为计算路径最大差值。
class Solution:def minimumEffortPath(self, heights: List[List[int]]) - int:n, m len(heights), len(heights[0])dist [0] [0x3f3f3f3f] * (n * m - 1)vis set()q [(0, 0, 0)]while q:d, x, y heappop(q)idx x * m yif idx in vis:continuevis.add(idx)for nx, ny in [(x - 1, y), (x 1, y), (x, y - 1), (x, y 1)]:if 0 nx n and 0 ny m:max_diff max(d, abs(heights[x][y] - heights[nx][ny]))if max_diff dist[nx * m ny]:dist[nx * m ny] max_diffheappush(q, (max_diff, nx, ny))return dist[-1]二分 BFS
class Solution:def minimumEffortPath(self, heights: List[List[int]]) - int:n, m len(heights), len(heights[0])def check(t):vis set()q collections.deque()q.append((0, 0))vis.add(0)while q:x, y q.popleft()for nx, ny in [(x - 1, y), (x 1, y), (x, y - 1), (x, y 1)]:if 0 nx n and 0 ny m and nx * m ny not in vis:max_diff abs(heights[x][y] - heights[nx][ny])if max_diff t:q.append((nx, ny))vis.add(nx * m ny)return m * n - 1 in visl, r 0, 10 ** 6 1while l r:mid (l r) // 2if check(mid):r midelse:l mid 1return l
