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

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

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

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

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

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

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

उदाहरण

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