打卡记录

最小体力消耗路径

链接

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 + y
            if idx in vis:
                continue
            vis.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_diff
                        heappush(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 vis

        l, r = 0, 10 ** 6 + 1
        while l < r:
            mid = (l + r) // 2
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l