पायथन में द्वीपों के बीच सबसे छोटे पुल की दूरी खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है, जहां 0 पानी का प्रतिनिधित्व करता है और 1 भूमि का प्रतिनिधित्व करता है। एक द्वीप 1s को 4 दिशाओं में जोड़ने का एक समूह है। द्वीप या तो 0s (पानी) से या किनारों से घिरे हुए हैं। हमें दो द्वीपों को जोड़ने वाले सबसे छोटे पुल की लंबाई ज्ञात करनी है।

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

तो आउटपुट 1 होगा। यह (1,0) से (1,2) पॉइंट्स को कनेक्ट करेगा।

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

• पंक्ति :=मैट्रिक्स की पंक्ति गणना

• col :=मैट्रिक्स की कॉलम संख्या

• फ़ंक्शन को परिभाषित करें dfs() । इसमें i, j, s

  . लगेगा

• अगर (i, j) s में है, तो

  • वापसी

• अगर mat[i, j] 0 के समान है, तो

  • वापसी

• (i, j) s में डालें

• अगर मैं - 1>=0, तो

  • dfs(i-1, j, s)

• अगर मैं + 1 <पंक्ति, तो

  • dfs(i + 1, j, s)

• अगर j - 1>=0, तो

  • dfs(i, j-1, s)

• अगर j + 1

  • dfs(i, j + 1, s)

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

• देखा :=एक नया सेट

• मैं के लिए 0 से पंक्ति की सीमा में, करते हैं

  • अगर देखा का आकार> 0, तो

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

  • j के लिए 0 से col की सीमा में, करें

    • अगर mat[i, j] 1 के समान है, तो

      • dfs(i, j, देखा गया)

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

• q :=एक डबल एंडेड कतार

• देखी गई प्रत्येक भूमि के लिए, करें

  • (i, j) :=भूमि

  • अगर i - 1>=0 और mat[i-1, j] 0 के समान है, तो

    • q के अंत में (i - 1, j, 1) डालें

  • अगर i + 1 <पंक्ति और चटाई [i + 1, j] 0 के समान है, तो

    • q के अंत में (i + 1, j, 1) डालें

  • अगर j - 1>=0 और mat[i, j-1] 0 के समान है, तो

    • q के अंत में (i, j-1, 1) डालें

  • अगर j + 1

    • q के अंत में (i, j + 1, 1) डालें

• जबकि q> 0 का आकार, करें

  • (i, j, dist) :=q का बायां आइटम, और q के बाईं ओर से आइटम हटाएं

  • अगर (i, j) दिखाई देता है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • मार्क (i, j) जैसा देखा गया है

  • अगर mat[i, j] 1 के समान है, तो

    • वापसी जिला - 1

  • अगर मैं - 1>=0, तो

    • q के अंत में (i - 1, j, dist + 1) डालें

  • अगर i + 1 <पंक्ति गैर-शून्य है, तो

    • q के अंत में (i + 1, j, dist + 1) डालें

  • अगर j - 1>=0, तो

    • q के अंत में (i, j-1, dist + 1) डालें

  • अगर j + 1

    • q के अंत में (i, j + 1, dist + 1) डालें

उदाहरण

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

import collections
class Solution:
   def solve(self, mat):
      row = len(mat)
      col = len(mat[0])
      def dfs(i, j, s):
         if (i, j) in s:
            return
         if mat[i][j] == 0:
            return
         s.add((i, j))
         if i - 1 >= 0:
            dfs(i - 1, j, s)
         if i + 1 < row:
            dfs(i + 1, j, s)
         if j - 1 >= 0:
            dfs(i, j - 1, s)
         if j + 1 < col:
            dfs(i, j + 1, s)
      seen = set()
      for i in range(row):
         if len(seen) > 0:
            break
         for j in range(col):
            if mat[i][j] == 1:
               dfs(i, j, seen)
               break
      q = collections.deque()
      for land in seen:
         i, j = land
         if i - 1 >= 0 and mat[i - 1][j] == 0:
            q.append((i - 1, j, 1))
         if i + 1 < row and mat[i + 1][j] == 0:
            q.append((i + 1, j, 1))
         if j - 1 >= 0 and mat[i][j - 1] == 0:
            q.append((i, j - 1, 1))
         if j + 1 < col and mat[i][j + 1] == 0:
            q.append((i, j + 1, 1))
      while len(q) > 0:
         i, j, dist = q.popleft()
         if (i, j) in seen:
            continue
         seen.add((i, j))
         if mat[i][j] == 1:
            return dist - 1
         if i - 1 >= 0:
            q.append((i - 1, j, dist + 1))
         if i + 1 < row:
            q.append((i + 1, j, dist + 1))
         if j - 1 >= 0:
            q.append((i, j - 1, dist + 1))
         if j + 1 < col:
            q.append((i, j + 1, dist + 1))
ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [1, 0, 0],
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

1