पायथन में दो स्थानों पर सोना लेने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स और कुछ अन्य मान जैसे row, col, erow0, ecol0, erow1, ecol1 हैं। यदि हमारी वर्तमान स्थिति matrix[row][col] है और हम matrix[erow0][ecol0] और matrix[erow1][ecol1] पर स्थित सोना लेना चाहते हैं। हम ऊपर, नीचे, बाएं, दाएं जा सकते हैं लेकिन जब हम सेल (r, c) पर होते हैं, तो हमें लागत matrix[r][c] चुकानी पड़ती है, हालांकि यदि हम किसी सेल पर एक से अधिक बार आते हैं, तो हमें उस सेल की लागत फिर से नहीं चुकानी पड़ती। दोनों स्थानों पर सोना लेने की न्यूनतम लागत ज्ञात करें।

उदाहरण के लिए, यदि मैट्रिक्स है:

1	1	1	1	1
1	10	10	10	10
1	1	1	10	10

row=0, col=0, erow0=0, ecol0=3, erow1=2, ecol1=2, तो आउटपुट 8 होगा।

एल्गोरिदम (डिज्क्स्ट्रा + मीटिंग पॉइंट)

is_valid(x, y) फ़ंक्शन परिभाषित करें जो जांचता है कि निर्देशांक मैट्रिक्स के भीतर हैं या नहीं
min_cost(sx, sy) फ़ंक्शन परिभाषित करें जो डिज्क्स्ट्रा एल्गोरिदम का उपयोग करके (sx, sy) से सभी सेल्स तक की न्यूनतम लागत लौटाता है
मुख्य विधि से:
- तीन स्रोतों (प्रारंभ, सोना1, सोना2) से min_cost चलाएं जिससे तीन दूरी मैट्रिक्स a, b, c प्राप्त हों
- प्रत्येक सेल (i, j) के लिए, कुल लागत a[i][j] + b[i][j] + c[i][j] - 2*matrix[i][j] की गणना करें (क्योंकि मीटिंग पॉइंट की लागत तीन बार गिनी जाती है)
- न्यूनतम कुल लागत वापस करें

उदाहरण

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]:
                        edge = matrix[nx][ny]
                        dists[nx][ny] = edge + cost
                        heapq.heappush(heap, (edge + cost, nx, ny))
            return dists
        res = math.inf
        a, b, c = min_cost(row, col), min_cost(erow0, ecol0), min_cost(erow1, ecol1)
        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))

इनपुट

[[1,1,1,1,1],[1,10,10,10,10],[1,1,1,10,10]], 0, 0, 0, 3, 2, 2