पायथन में पूरी तरह से पानी से घिरे सभी द्वीपों को हटाने का कार्यक्रम

मान लीजिए कि हमारे पास एक द्विआधारी मैट्रिक्स है जहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है। और एक द्वीप 1 का समूह है जो 0s (पानी) या किनारों से घिरा हुआ है। हमें उन सभी द्वीपों को ढूंढना है जो पूरी तरह से पानी से घिरे हुए हैं और उन्हें 0s में संशोधित करना है। जैसा कि हम जानते हैं कि एक द्वीप पानी से घिरा हुआ है यदि सभी पड़ोसी (क्षैतिज और लंबवत विकर्ण नहीं) 0s हैं (पड़ोसी किनारों में से कोई भी नहीं है)।

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

तो आउटपुट होगा

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

• पंक्ति :=A की पंक्ति गणना

• col :=A की कॉलम संख्या

• B :=आकार A का एक मैट्रिक्स और 0 से भरें

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

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

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

    • अगर i और j मैट्रिक्स की रेंज में नहीं हैं, तो

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

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

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

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

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

    • d:=एक तत्व के साथ एक डबल एंडेड कतार (i, j)

    • जबकि d एम्प्री नहीं है, करें

      • (x, y) :=d का बायां तत्व, और d से हटाएं

      • बी [एक्स, वाई] :=1

      • (x, y) के प्रत्येक पड़ोसी (x2, y2) के लिए करें

        • अगर (x2, y2) दिखाई नहीं दे रहा है, तो

          • d के अंत में (x2, y2) डालें

          • (x2, y2) को देखा के रूप में चिह्नित करें

• वापसी बी

उदाहरण

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

from collections import deque
class Solution:
   def solve(self, A):
      row = len(A)
      col = len(A[0])
      B = [[0 for _ in range(col)] for _ in range(row)]
      seen = set()
      def nei(i, j):
         if i + 1 < row and A[i + 1][j]:
            yield (i + 1, j)
         if j + 1 < col and A[i][j + 1]:
            yield (i, j + 1)
         if i - 1 >= 0 and A[i - 1][j]:
            yield (i - 1, j)
         if j - 1 >= 0 and A[i][j - 1]:
            yield (i, j - 1)
         for i in range(row):
            for j in range(col):
               if i not in (0, row - 1) and j not in (0, col - 1):
                  continue
               if (i, j) in seen:
                  continue
               if A[i][j] == 0:
                  continue
               d = deque([(i, j)])
               while d:
                  x, y = d.popleft()
                  B[x][y] = 1
                  for x2, y2 in nei(x, y):
                     if (x2, y2) not in seen:
                        d.append((x2, y2))
                        seen.add((x2, y2))
         return B
ob = Solution()
matrix = [
   [1, 0, 0, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 1],
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

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