पायथन में 2D मैट्रिक्स में अलग-अलग द्वीपों की संख्या खोजें

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

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

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

समाधान दृष्टिकोण

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

• दो विधियां होंगी: एक द्वीपों की गिनती के लिए numIslands() और दूसरी makeWater()। makeWater() इस तरह होगी:
  • यदि ग्रिड में पंक्तियों की संख्या 0 है, तो 0 लौटाएं।
  • n = पंक्ति गिनती और m := स्तंभ गिनती, और ans := 0
  • i को 0 से n-1 तक:
    • j को 0 से m-1 तक:
      • यदि 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) कॉल करें।
  • makeWater(i-1, j, n, m, grid) कॉल करें।
  • makeWater(i, j-1, n, m, grid) कॉल करें।

उदाहरण

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

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)

इनपुट

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

आउटपुट

3