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

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

इसलिए, यदि इनपुट इस प्रकार है:

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

हल करने के चरण

• row := A की पंक्तियों की संख्या

• col := A के स्तंभों की संख्या

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

• seen := एक नया सेट

• i के लिए 0 से row तक की रेंज में, करें

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

    • यदि i और j मैट्रिक्स की रेंज में नहीं हैं, तो अगले इटरेशन पर जाएं

    • यदि (i, j) seen है, तो अगले इटरेशन पर जाएं

    • यदि A[i, j], 0 के समान है, तो अगले इटरेशन पर जाएं

    • d := एक एलिमेंट (i, j) के साथ डबल एंडेड क्यू

    • जब तक d खाली नहीं है, करें

      • (x, y) := d का बायां एलिमेंट, और d से हटाएं

      • B[x, y] := 1

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

        • यदि (x2, y2) seen नहीं है, तो

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

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

• B लौटाएं

उदाहरण

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]]