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

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां कुछ मान इस प्रकार हैं:

• 0 एक खाली सेल को दर्शाता है।
• 1 एक दीवार को दर्शाता है।
• 2 एक व्यक्ति को दर्शाता है।

यहां एक व्यक्ति इन चार दिशाओं (ऊपर, नीचे, बाएं और दाएं) में से किसी में भी चल सकता है। हमें एक ऐसा सेल ढूंढना है जो दीवार नहीं है ताकि यह कुल यात्रा दूरी को कम से कम करे जो प्रत्येक व्यक्ति को चलना है और अंत में दूरी ढूंढें।

तो, यदि इनपुट इस तरह है

तो आउटपुट 7 होगा क्योंकि सबसे अच्छा मीटिंग पॉइंट निचला दायां कोना है।

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

• twos := एक नया मैप, costs := एक नया मैप
• प्रत्येक इंडेक्स i और पंक्ति r मैट्रिक्स में के लिए, करें
  • प्रत्येक इंडेक्स j और मान v r में के लिए, करें
    • यदि v, 2 के समान है, तो
      • twos[i, j] := [i, j, 0]
      • costs[i, j] := दिए गए मैट्रिक्स के आकार का एक 2D मैट्रिक्स बनाएं और अनंत से भरें
• twos में प्रत्येक कुंजी-मान जोड़ी (k, q) के लिए, करें
  • seen := एक नया सेट
  • जब q खाली नहीं है, तो करें
    • (i, j, cost) := q से पहला तत्व हटाएं
    • यदि (i, j) seen में है, तो अगले पुनरावृत्ति के लिए जाएं
    • (i, j) को seen में जोड़ें
    • costs[k, i, j] := cost
    • प्रत्येक (di, dj) में ((1, 0), (-1, 0), (0, 1), (0, -1)) के लिए, करें
      • (ni, nj) := (i + di, j + dj)
      • यदि ni और nj मैट्रिक्स की रेंज में हैं और matrix[ni, nj], 1 नहीं है, तो
        • (ni, nj, cost + 1) को q के अंत में डालें
• ans := अनंत
• i को 0 से मैट्रिक्स की पंक्ति संख्या तक की रेंज में लिए, करें
  • j को 0 से मैट्रिक्स की कॉलम संख्या तक की रेंज में लिए, करें
    • cur_cost := 0
    • costs के सभी मानों की सूची में प्रत्येक arr के लिए, करें
      • cur_cost := cur_cost + arr[i, j]
    • ans := ans और cur_cost का न्यूनतम
• ans लौटाएं

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

उदाहरण

class Solution:
    def solve(self, matrix):
        twos = {}
        costs = {}
        for i, r in enumerate(matrix):
            for j, v in enumerate(r):
                if v == 2:
                    twos[(i, j)] = [(i, j, 0)]
                    costs[(i, j)] = [[1e9 for _ in matrix[0]] for _ in matrix]
        for k, q in twos.items():
            seen = set()
            while q:
                i, j, cost = q.pop(0)
                if (i, j) in seen:
                    continue
                seen.add((i, j))
                costs[k][i][j] = cost
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if (ni >= 0 and nj >= 0 and ni < len(matrix) and nj < len(matrix[0]) and matrix[ni][nj] != 1):
                        q.append((ni, nj, cost + 1))
        ans = 1e9
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                cur_cost = 0
                for arr in costs.values():
                    cur_cost += arr[i][j]
                ans = min(ans, cur_cost)
        return ans

ob = Solution()
matrix = [
    [2, 0, 1, 0],
    [1, 0, 1, 2],
    [0, 0, 2, 2]
]
print(ob.solve(matrix))

इनपुट

matrix = [ [2, 0, 1, 0], [1, 0, 1, 2], [0, 0, 2, 2] ]

आउटपुट

7