Problem statement

https://binarysearch.com/problems/Hill-Maker/

Solution

The idea is to look at this problem as shortest path problem in graph. We start from the right bottom corner and have states (r, c, h), where r and c are coordinates and h is current height. For each node we check 4 neighbours and see what cost we need to pay to visit them.

Complexity

We have O(mnH) states, where H is number of different values in matrix. So, time complexity is O(mnH*log(mnH)) for time and O(mnH) for space.

Code

#### awice code
class Solution:
    def solve(self, A):
        INF = float("inf")
        n, m = len(A), len(A[0])

        pq = [[0, n - 1, m - 1, A[-1][-1]]]
        dist = collections.defaultdict(lambda: INF)
        dist[n - 1, m - 1, A[-1][-1]] = 0
        while pq:
            d, r, c, h = heapq.heappop(pq)
            if dist[r, c, h] < d:
                continue
            if r + c == 0:
                return d
            for nr, nc in [[r + 1, c], [r, c + 1], [r - 1, c], [r, c - 1]]:
                if 0 <= nr < n and 0 <= nc < m:
                    h2 = max(A[nr][nc], h)
                    d2 = d + max(h2 - A[nr][nc], 0)
                    if d2 < dist[nr, nc, h2]:
                        dist[nr, nc, h2] = d2
                        heapq.heappush(pq, [d2, nr, nc, h2])