पायथन में द्वीपों की संख्या

मान लीजिए हमारे पास एक ग्रिड है, जिसमें कुछ 0 और कुछ 1 हैं। हमें द्वीपों की संख्या गिननी है। एक द्वीप वह स्थान है जो पानी से घिरा हुआ है और क्षैतिज या लंबवत रूप से आसन्न भूमि को जोड़कर बनता है। हम मान सकते हैं कि ग्रिड के सभी चार किनारे पानी से घिरे हुए हैं।

मान लीजिए ग्रिड इस तरह है -

यहां तीन द्वीप हैं।

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

• दो मेथड होंगे, एक द्वीपों की संख्या गिनने के लिए numIslands() और makeWater()। makeWater() इस तरह होगा -
• यदि ग्रिड में पंक्तियों की संख्या 0 है, तो 0 लौटाएं
• n = पंक्ति संख्या और m := कॉलम संख्या, और ans := 0
• i को 0 से n - 1 तक की रेंज में
  • j को 0 से m तक की रेंज में
    • यदि grid[i, j] = 1, तो ans := ans + 1
    • makeWater(i, j, n, m, grid)
• makeWater() इंडेक्स i, j, पंक्ति और कॉलम संख्या n और m, और ग्रिड लेगा
• यदि i < 0 या j < 0 या i >= n या j >= m, तो इस मेथड से लौट जाएं
• यदि grid[i, j] = 0, तो लौट जाएं अन्यथा grid[i, j] := 0 करें
• makeWater(i + 1, j, n, m, grid) कॉल करें
• makeWater(i, j + 1, n, m, grid) कॉल करें

यह DFS (डेप्थ-फर्स्ट सर्च) का उपयोग करके विज़िटेड लैंड को पानी में बदल देता है।

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

उदाहरण

class Solution(object):
    def numIslands(self, grid):
        if len(grid) == 0:
            return 0
        n = len(grid)
        m = len(grid[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    ans += 1
                    self.make_water(i, j, n, m, grid)
        return ans

    def make_water(self, i, j, n, m, grid):
        if i < 0 or j < 0 or i >= n or j >= m:
            return
        if grid[i][j] == "0":
            return
        else:
            grid[i][j] = "0"
        self.make_water(i + 1, j, n, m, grid)
        self.make_water(i, j + 1, n, m, grid)
        self.make_water(i - 1, j, n, m, grid)
        self.make_water(i, j - 1, n, m, grid)

ob1 = Solution()
print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]))

इनपुट

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

आउटपुट

3