Chương trình tìm tổng tăng chiều cao tối thiểu để đến đích trên ma trận trong Python

Cho ma trận biểu diễn độ cao. Từ góc trên trái đến góc dưới phải, chỉ được đi ô kề (lên/xuống/trái/phải) nếu độ cao ô kế ≤ độ cao ô hiện tại. Có thể tăng độ cao các ô trước khi đi. Tìm tổng tăng độ cao tối thiểu.

Ví dụ: ma trận 2x3 → kết quả 4.

Giải thuật (Dijkstra trên trạng thái (r, c, h))

Trạng thái: vị trí và độ cao hiện tại (max độ cao trên đường đi). Chi phí = tổng tăng độ cao.

1. Priority queue khởi tạo (từ đích ngược về nguồn).
2. = chi phí nhỏ nhất.
3. Pop trạng thái chi phí nhỏ nhất:
   • Nếu về (0,0): trả về chi phí.
   • Mở rộng 4 hướng: , .
   • Nếu : cập nhật và push vào pq.

Ví dụ minh họa

import collections
import heapq

class Solution:
    def solve(self, A):
        INF = float('inf')
        R, C = len(A), len(A[0])
        pq = [[0, R-1, C-1, A[-1][-1]]]
        dist = collections.defaultdict(lambda: INF)
        dist[R-1, C-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 < R and 0 <= nc < C:
                    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])

ob = Solution()
matrix = [[2, 4, 5], [8, 6, 1]]
print(ob.solve(matrix))  # Output: 4

Đầu vào

[[2, 4, 5], [8, 6, 1]]

Đầu ra

4