Python矩陣中被包圍島嶼數量計數程式

假設我們有一個二進位制矩陣。其中1代表陸地，0代表水。眾所周知，島嶼是由一群聚集在一起的1組成的，其周長被水包圍。我們必須找到完全被包圍的島嶼的數量。

所以，如果輸入是這樣的：

那麼輸出將是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 and b and c and d
  • 在主方法中執行以下操作：
  • R := 矩陣的行數，C := 矩陣的列數
  • ans := 0
  • 對於i在0到R範圍內：
    • 對於j在0到C範圍內：
      • 如果matrix[i, j]等於1，則
        • 如果dfs(i, j)為真，則
          • ans := ans + 1
  • 返回ans

讓我們看看下面的實現以更好地理解：

示例

線上演示

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

更新於：2020年12月2日

瀏覽量：508

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.