โปรแกรมหาความสูงที่ต้องเพิ่มน้อยที่สุดเพื่อไปถึงปลายทางในเมทริกซ์ด้วย Python

สมมติว่าเรามีเมทริกซ์ M ที่ M[r][c] คือความสูงของเซลล์ เริ่มจากมุมซ้ายบน ต้องไปมุมขวาล่าง สามารถเดินได้เฉพาะเซลล์ติดกัน (บน/ล่าง/ซ้าย/ขวา) ก็ต่อเมื่อความสูงเซลล์ปลายทาง <= เซลล์ปัจจุบัน เราสามารถเพิ่มความสูงเซลล์ได้ก่อนเดิน ต้องการหาผลรวมความสูงที่เพิ่มน้อยที่สุด

ตัวอย่าง:

2 4 5
8 6 1

ขั้นตอนการแก้ปัญหา (Dijkstra / Priority Queue)

1. ใช้ Priority Queue (min-heap) เก็บ [cost, row, col, height] เริ่มจากปลายทาง
2. dist[(r, c, h)] = ต้นทุนน้อยที่สุดถึง (r,c) ด้วยความสูง h
3. Pop สถานะที่ cost น้อยที่สุด:
   • หากถึง (0,0) คืนค่า cost
   • สำหรับเพื่อนบ้าน 4 ทิศทาง:
     • h2 = max(A[nr][nc], h) (ความสูงใหม่)
     • d2 = d + max(h2 - A[nr][nc], 0) (ต้นทุนเพิ่ม)
     • อัปเดตถ้า d2 < dist[nr, nc, h2]

ตัวอย่างโค้ด Python

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 == 0 and 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

อินพุต

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

เอาต์พุต

4