Leetcode 1753 Solution

This article provides solution to leetcode question 1753 (path-with-minimum-effort)
Categories:
Tags:
Access this page by simply typing in "lcs 1753" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/path-with-minimum-effort

Solution

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        q = []
        heapq.heappush(q, (0, 0, 0))

        m = len(heights)
        n = len(heights[0])

        visited = [[-1 for _ in range(n)] for _ in range(m)]

        while q:
            min_effort, i, j = heapq.heappop(q)

            if visited[i][j] != -1:
                continue

            if i == m - 1 and j == n - 1:
                return min_effort

            visited[i][j] = min_effort

            neighs = [
                (i - 1, j),
                (i + 1, j),
                (i, j - 1),
                (i, j + 1),
            ]

            for neigh_i, neigh_j in neighs:
                if not 0 <= neigh_i < m or not 0 <= neigh_j < n:
                    continue

                heapq.heappush(q, (max(min_effort, int(abs(heights[neigh_i][neigh_j] - heights[i][j]))), neigh_i, neigh_j))