Manjusaka

09-16 leetcode-1631

链接 1631. Path With Minimum Effort

题目

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

题解

这题解法比较多，我今天偷懒先 BFS 切了

import heapq
from collections import namedtuple

Direction = namedtuple("Direction", ["x", "y"])
Flag = 10 ** 6


class Solution:
    directions = [Direction(x, y) for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]]

    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        heap = [(0, 0, 0)]
        distance_index = [[Flag] * len(heights[0]) for _ in range(len(heights))]
        while heap:
            delta, x, y = heapq.heappop(heap)
            if delta > distance_index[x][y]:
                continue
            if x == len(heights) - 1 and y == len(heights[0]) - 1:
                return delta
            for direction in self.directions:
                new_x, new_y = x + direction.x, y + direction.y
                if 0 <= new_x < len(heights) and 0 <= new_y < len(heights[0]):
                    new_delta = max(delta, abs(heights[x][y] - heights[new_x][new_y]))
                    if new_delta < distance_index[new_x][new_y]:
                        distance_index[new_x][new_y] = new_delta
                        heapq.heappush(heap, (new_delta, new_x, new_y))