पायथन में किसी भी सेल में सभी व्यक्तियों से मिलने के लिए आवश्यक न्यूनतम चरणों की संख्या खोजने का कार्यक्रम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां ये मान मौजूद हैं:0 एक खाली सेल का प्रतिनिधित्व करता है। 1 एक दीवार का प्रतिनिधित्व करता है। 2 एक व्यक्ति का प्रतिनिधित्व करता है। अब कोई व्यक्ति ऊपर, नीचे, बाएँ, दाएँ चारों दिशाओं में से किसी भी दिशा में चल सकता है अन्यथा एक समय इकाई में रह सकता है। हमें एक चलने योग्य सेल की तलाश करनी है ताकि यह सभी को मिलने और समय वापस करने में लगने वाले समय को कम से कम कर सके। हमें यह ध्यान रखना होगा कि एक ही खाली सेल में दो लोग चल सकते हैं और आप मान सकते हैं कि किन्हीं दो लोगों के बीच हमेशा कोई न कोई रास्ता होता है।

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

तो आउटपुट 2 होगा, क्योंकि सभी अधिकतम 2 चरणों के साथ स्थिति मैट्रिक्स [1, 1] पर मिल सकते हैं।

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

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

• फ़ंक्शन को परिभाषित करें bfs() । इसमें r, c

  . लगेगा

• कतार :=एक कतार को परिभाषित करें और उसमें एक जोड़ी (r, c) डालें

• जिला :=कुंजी मान युग्म के साथ एक नक्शा {(r, c) :0}

• कतार में प्रत्येक जोड़ी (आर, सी) के लिए, करें

  • अगर dist[r, c]> 15 गैर-शून्य है, तो

    • लूप से बाहर आएं

  • (आर, सी) के प्रत्येक पड़ोसी (एनआर, एनसी) के लिए, करो

    • अगर (एनआर, एनसी) जिले में नहीं है, तो

      • जिला [एनआर, एनसी]:=जिला [आर, सी] + 1

      • कतार के अंत में डालें (एनआर, एनसी)

  • वापसी जिला

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

• जिला :=शून्य

• प्रत्येक पंक्ति संख्या r और A के संगत पंक्ति तत्वों के लिए, करें

  • प्रत्येक स्तंभ संख्या c और पंक्ति के मान [c] वैल के लिए, करें

    • अगर वैल 2 के समान है, तो

      • ndist :=bfs(r, c)

      • यदि जिला रिक्त है, तो

        • जिला :=ndist

      • अन्यथा,

        • डिस्ट की चाबियों में प्रत्येक कुंजी के लिए, करें

          • अगर कुंजी ndist में है, तो

            • डिस्ट [कुंजी]:=अधिकतम जिला [कुंजी], एनडिस्ट [कुंजी]

          • अन्यथा,

            • डिस्ट [कुंजी] को हटा दें

• अगर डिस्टर्ब खाली नहीं है तो डिस्ट के सभी मानों में से कम से कम लौटाएं, अन्यथा 0 पर लौटें

उदाहरण

class Solution:
def solve(self, A):
   R, C = len(A), len(A[0])
   def get_neighbor(r, c):
      for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
         if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
            yield nr, nc
      def bfs(r, c):
         queue = [(r, c)]
         dist = {(r, c): 0}
         for r, c in queue:
            if dist[r, c] > 15:
               break
            for nr, nc in get_neighbor(r, c):
               if (nr, nc) not in dist:
                  dist[nr, nc] = dist[r, c] + 1
                  queue.append((nr, nc))
         return dist
      dist = None
      for r, row in enumerate(A):
         for c, val in enumerate(row):
            if val == 2:
               ndist = bfs(r, c)
               if dist is None:
                  dist = ndist
               else:
                  for key in list(dist.keys()):
                     if key in ndist:
                        dist[key] = max(dist[key],ndist[key])
                     else:
                        del dist[key]
      return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0]
]
print(ob.solve(matrix))

इनपुट

[
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0] 
]

आउटपुट

2