Pythonの行列で最大の島の領域を見つけるプログラム

バイナリ行列があるとします。ここで、1は土地を表し、0は水を表します。また、島は、周囲が水に囲まれている隣接する1のグループです。マトリックスのエッジは水に囲まれていると想定できます。マトリックス内で最大の島の面積を見つける必要があります。

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

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

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

• 関数dfs（）を定義します。これは行列、r、cを取ります
• 合計：=合計+ 1
• matrix [r、c]：=0
• r --1> =0で、matrix [r --1、c]が1と同じ場合、
  • dfs（matrix、r-1、c）
• c --1> =0で、matrix [r、c --1]が1と同じ場合、
  • dfs（matrix、r、c-1）
• r +1
• dfs（matrix、r + 1、c）

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

例

class Solution:
   def solve(self, matrix):
      self.r_len = len(matrix)
      self.c_len = len(matrix[0])
      max_island = 0
      for r in range(self.r_len):
         for c in range(self.c_len):
            if matrix[r][c] == 1:
               self.total = 0
               self.dfs(matrix, r, c)
               max_island = max(max_island, self.total)
      return max_island
   def dfs(self, matrix, r, c):
      self.total += 1
      matrix[r][c] = 0
      if r - 1 >= 0 and matrix[r - 1][c] == 1:
         self.dfs(matrix, r - 1, c)
      if c - 1 >= 0 and matrix[r][c - 1] == 1:
         self.dfs(matrix, r, c - 1)
      if r + 1 < self.r_len and matrix[r + 1][c] == 1:
         self.dfs(matrix, r + 1, c)
      if c + 1 < self.c_len and matrix[r][c + 1] == 1:
         self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]
print(ob.solve(matrix))

入力

matrix = [
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0] ]

出力

6