Pythonで行列内の囲まれた島の数を数えるプログラム

バイナリ行列があるとします。ここで、1は土地を表し、0は水を表します。私たちが知っているように、島は周囲が水に囲まれているグループ化された1のグループです。完全に囲まれた島の数を見つける必要があります。

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

3つの島があるため、出力は2になりますが、そのうちの2つは完全に囲まれています。

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

• 関数dfs（）を定義します。これにはi、jが必要です
• iとjが行列の範囲内にない場合、
  • Falseを返す
• matrix [i、j]が0と同じ場合、
  • Trueを返す
• matrix [i、j]：=0
• a：=dfs（i + 1、j）
• b：=dfs（i-1、j）
• c：=dfs（i、j + 1）
• d：=dfs（i、j-1）
• aとbとcとdを返す
• メインの方法から次の手順を実行します。
• R：=行列の行数、C：=行列の列数
• ans：=0
• 0からRの範囲のiについては、
  • 0からCの範囲のjについては、
    • matrix [i、j]が1と同じ場合、
      • dfs（i、j）がtrueの場合、
        • ans：=ans + 1
• 回答を返す

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

例

class Solution:
   def solve(self, matrix):
      def dfs(i, j):
         if i < 0 or j < 0 or i >= R or j >= C:
            return False
         if matrix[i][j] == 0:
            return True
         matrix[i][j] = 0
         a = dfs(i + 1, j)
         b = dfs(i - 1, j)
         c = dfs(i, j + 1)
         d = dfs(i, j - 1)
         return a and b and c and d

      R, C = len(matrix), len(matrix[0])
      ans = 0
      for i in range(R):
         for j in range(C):
            if matrix[i][j] == 1:
               if dfs(i, j):
                  ans += 1
      return ans

ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [0, 0, 0, 1, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0]
]
print(ob.solve(matrix))

入力

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

出力

2