Chương trình đếm số đảo trong một ma trận nhất định bằng Python

Giả sử chúng ta có một ma trận nhị phân, chúng ta phải tìm số đảo trong ma trận. Ở đây 1 là đất và 0 là nước, vì vậy một hòn đảo là một nhóm các đảo 1 lân cận và có chu vi được bao quanh bởi nước. Ở đây chúng tôi đang xem xét các hàng xóm chỉ có thể là ngang hoặc dọc, không phải là đường chéo.

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

thì đầu ra sẽ là 4.

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

• Xác định một hàm explore (). Điều này sẽ lấy hàng, cột, ma trận
• nếu hàng và cột không nằm trong phạm vi của ma trận hoặc ma trận [hàng, cột] là 0, thì
  • trở lại
• ma trận [row, col]:=0
• khám phá (hàng + 1, cột, ma trận)
• khám phá (hàng - 1, cột, ma trận)
• khám phá (hàng, cột + 1, ma trận)
• khám phá (hàng, cột - 1, ma trận)
• Từ phương pháp chính, hãy thực hiện như sau -
• nếu ma trận là null, thì
  • trả về 0
• đảo:=0
• đối với hàng trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện
  • đối với col trong phạm vi 0 đến số cột của ma trận, hãy thực hiện
    • nếu ma trận [row, col] giống 1, thì
      • đảo:=đảo + 1
      • khám phá (hàng, cột, ma trận)
• đảo trở lại

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

Đầu vào

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

Đầu ra

4