Chương trình đếm số hòn đảo bao quanh trong ma trận trong python

Giả sử chúng ta có một ma trận nhị phân. Trong đó 1 đại diện cho đất và 0 đại diện cho nước. Như chúng ta đã biết, một hòn đảo là một nhóm 1 được nhóm lại với nhau có chu vi được bao quanh bởi nước. Chúng ta phải tìm số lượng các hòn đảo bị bao vây hoàn toàn.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, vì có ba hòn đảo, nhưng hai trong số chúng bị bao quanh hoàn toàn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm dfs (). Điều này sẽ mất tôi, j
• nếu i và j không thuộc phạm vi của ma trận, thì
  • trả về Sai
• nếu ma trận [i, j] giống 0, thì
  • trả về True
• ma trận [i, j]:=0
• a:=dfs (i + 1, j)
• b:=dfs (i - 1, j)
• c:=dfs (i, j + 1)
• d:=dfs (i, j - 1)
• trả về a và b và c và d
• Từ phương thức chính, hãy làm như sau:
• R:=số hàng của ma trận, C:=số cột của ma trận
• ans:=0
• đối với tôi trong phạm vi từ 0 đến R, thực hiện
  • đối với j trong phạm vi từ 0 đến C, thực hiện
    • nếu ma trận [i, j] giống 1, thì
      • nếu dfs (i, j) là true, thì
        • ans:=ans + 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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] ]

Đầu ra

2