Chương trình tìm chi phí nhỏ nhất nhặt vàng tại 2 vị trí trong ma trận Python

Cho ma trận chi phí matrix, vị trí bắt đầu (row, col) và 2 vị trí vàng (erow0, ecol0), (erow1, ecol1). Di chuyển 4 hướng, chi phí vào ô (r,c) là matrix[r][c] (chỉ tính 1 lần nếu đi qua lại). Tìm chi phí nhỏ nhất để nhặt được cả 2 vàng.

Ví dụ ma trận 3x5, bắt đầu (0,0), vàng tại (0,3) và (2,2) → kết quả 8.

Giải thuật (Dijkstra 3 lần + Giao điểm tối ưu)

1. Chạy Dijkstra từ 3 điểm: start, gold0, gold1 → được 3 ma trận khoảng cách a, b, c.
2. Duyệt mọi ô (i,j) làm điểm gặp gộ (meeting point). Chi phí tổng = a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j] (trừ chi phí ô gặp gộ tính 3 lần).
3. Lấy min của tổng chi phí trên.

Ví dụ minh họa

import heapq, math

class Solution:
    def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
        def is_valid(x, y):
            return 0 <= x < len(matrix) and 0 <= y < len(matrix[0])
        
        def min_cost(sx, sy):
            heap = [(matrix[sx][sy], sx, sy)]
            dists = [[math.inf] * len(matrix[0]) for _ in range(len(matrix))]
            dists[sx][sy] = matrix[sx][sy]
            while heap:
                cost, x, y = heapq.heappop(heap)
                for nx, ny in [(x, y-1), (x+1, y), (x-1, y), (x, y+1)]:
                    if is_valid(nx, ny) and matrix[nx][ny] + cost < dists[nx][ny]:
                        dists[nx][ny] = matrix[nx][ny] + cost
                        heapq.heappush(heap, (dists[nx][ny], nx, ny))
            return dists
        
        a = min_cost(row, col)
        b = min_cost(erow0, ecol0)
        c = min_cost(erow1, ecol1)
        
        res = math.inf
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j])
        return res

ob = Solution()
matrix = [[1,1,1,1,1],[1,10,10,10,10],[1,1,1,10,10]]
print(ob.solve(matrix, 0, 0, 0, 3, 2, 2))  # Output: 8

Đầu vào / Đầu ra

Input: matrix, 0, 0, 0, 3, 2, 2

Output: 8