Pythonで特定の行列の島の数を数えるプログラム

バイナリ行列があるとすると、行列内の島の数を見つける必要があります。ここで、1は土地用、0は水用です。したがって、島は隣接し、周囲が水に囲まれている1のグループです。ここでは、隣接するものは水平または垂直のみであり、対角線ではないと考えています。

したがって、入力が次のような場合

その場合、出力は4になります。

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

• 関数explore（）を定義します。これには、行、列、行列が必要です
• 行と列が行列の範囲内にないか、matrix [row、col]が0の場合、
  • 戻る
• matrix [row、col]：=0
• explore（row + 1、col、matrix）
• explore（row-1、col、matrix）
• explore（row、col + 1、matrix）
• explore（row、col-1、matrix）
• メインの方法から、次の手順を実行します-
• 行列がnullの場合、
  • 0を返す
• 島：=0
• 0から行列の行数までの範囲の行については、
  • 0から行列の列数までの範囲の列については、
    • matrix [row、col]が1と同じ場合、
      • 島：=島+1
      • explore（row、col、matrix）
• 島を返す

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

例

class Solution:
   def explore(self, row, col, matrix):
   if (
         row < 0 or col < 0 or row > len(matrix) - 1 or col > len (matrix[0]) - 1 or          matrix[row][col] == 0):
         return
      matrix[row][col] = 0
      self.explore(row + 1, col, matrix)
      self.explore(row - 1, col, matrix)
      self.explore(row, col + 1, matrix)
      self.explore(row, col - 1, matrix)
      def solve(self, matrix):
         if not matrix:
            return 0
         islands = 0
         for row in range(len(matrix)):
            for col in range(len(matrix[0])):
               if matrix[row][col] == 1:
                  islands += 1
                  self.explore(row, col, matrix)
         return islands
ob = Solution() matrix = [
   [1, 0, 1, 0, 0],
   [0, 0, 1, 0, 0],
   [0, 1, 1, 0, 0],
   [0, 0, 0, 0, 0],
   [1, 1, 0, 1, 1],
   [1, 1, 1, 0, 1]
]
print(ob.solve(matrix))

入力

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

出力

4