Pythonの島の数

グリッドがあり、0と1が少ないとします。島の数を数えなければなりません。島とは、水に囲まれ、隣接する土地を水平または垂直につなぐことで形成される場所です。グリッドの4つのエッジすべてがすべて水に囲まれていると想定できます。

グリッドが-

3つの島があります。

これを解決するには、次の手順に従います-

• 2つのメソッドがあります。1つはnumIslands（）およびmakeWater（）と呼ばれる島の数をカウントするために使用されます。 makeWater（）は次のようになります-
• グリッドの行数が0の場合、0を返します
• n =行数およびm：=列数、およびans：=0
• 0からn–1の範囲のiの場合
  • 0からmの範囲のjの場合
    • grid [i、j] =1の場合、ans：=ans + 1
    • makeWater（i、j、n、m、グリッド）
• 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）を呼び出す

理解を深めるために、次の実装を見てみましょう-

例

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