पायथन में दिए गए दो स्थानों में सोना लेने के लिए न्यूनतम लागत खोजने का कार्यक्रम

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

तो, अगर इनपुट पसंद है

पंक्ति =0, col =0, erow0 =0, ecol0 =3, erow1 =2, ecol1 =2, तो आउटपुट 8 होगा, क्योंकि हम (0, 0) पर हैं और स्थान से सोना चुनना चाहते हैं (0, 3) और (2, 2)। इसलिए पहले (0, 0) से (0, 3) तक तीन कदम आगे बढ़ें फिर (0,0) पर वापस आएं फिर 1 चिह्नित सेल का अनुसरण करके (2, 2) पर जाएं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें is_valid() । इसमें x, y लगेगा

• जब x और y मैट्रिक्स की सीमा में हों, तो सही लौटें, अन्यथा असत्य

• एक फ़ंक्शन को परिभाषित करें min_cost() । इसमें sx, sy

  . लगेगा

• ढेर:=आइटम के साथ एक ढेर (मैट्रिक्स [sx, sy], sx, sy)

• dists :=दिए गए मैट्रिक्स के समान आकार का एक मैट्रिक्स और inf से भरें

• dists[sx, sy] :=matrix[sx, sy]

• जबकि ढेर खाली नहीं है, करें

  • (लागत, x, y) :=ढेर का पहला तत्व और ढेर से पहला तत्व हटाएं

  • [(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1)] में प्रत्येक जोड़ी (nx, ny) के लिए, करें

    • यदि is_valid(nx, ny) और मैट्रिक्स[nx, ny] + लागत

      • किनारे:=मैट्रिक्स [एनएक्स, एनवाई]

      • dists[nx, ny] :=edge + cost

      • ढेर में डालें (किनारे + लागत, एनएक्स, एनवाई)

• वापसी जिले

• मुख्य विधि से निम्न कार्य करें -

• रेस :=inf

• a :=min_cost(row, col), b :=min_cost(erow0, ecol0), c :=min_cost(erow1, ecol1)

• मैं के लिए 0 से लेकर मैट्रिक्स की पंक्ति गणना तक, करें

  • j के लिए रेंज 0 से लेकर मैट्रिक्स की कॉलम काउंट तक, करें

    • रेस :=न्यूनतम रेस और (a[i, j] + b[i, j] + c[i, j] - 2 * matrix[i, j])

• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import heapq
import math
class Solution:
   def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
      def is_valid(x, y):
         return x >= 0 and y >= 0 and x < len(matrix) and 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]
]
row = 0
col = 0
erow0 = 0
ecol0 = 3
erow1 = 2
ecol1 = 2
print(ob.solve(matrix, row, col, erow0, ecol0, erow1, ecol1))

इनपुट

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

आउटपुट

8