Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm diện tích hòn đảo lớn nhất trong ma trận bằng Python

Giả sử chúng ta có một ma trận nhị phân. Ở đây 1 đại diện cho đất và 0 đại diện cho nước, Và một hòn đảo là một nhóm các 1 nằm lân cận với chu vi được bao quanh bởi nước. Chúng ta có thể giả định rằng các cạnh của ma trận được bao quanh bởi nước. Chúng ta phải tìm diện tích của hòn đảo lớn nhất trong ma trận.

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

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

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

Để 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ẽ lấy ma trận, r, c
  • tổng số:=tổng số + 1
  • ma trận [r, c]:=0
  • nếu r - 1> =0 và ma trận [r - 1, c] giống 1 thì
    • dfs (ma trận, r - 1, c)
  • nếu c - 1> =0 và ma trận [r, c - 1] giống 1 thì
    • dfs (ma trận, r, c - 1)
  • nếu r + 1
  • dfs (ma trận, r + 1, c)
  • nếu c + 1
  • dfs (ma trận, r, c + 1)
  • Từ phương pháp chính, hãy thực hiện như sau -
  • r_len:=số hàng của ma trận
  • c_len:=số cột của ma trận
  • max_island:=0
  • đối với r trong phạm vi từ 0 đến r_len - 1, thực hiện
    • đối với c trong phạm vi từ 0 đến c_len - 1, thực hiện
      • nếu ma trận [r, c] giống 1, thì
        • tổng số:=0
        • dfs (ma trận, r, c)
        • max_island:=tối đa là max_island, tổng số
  • trả về max_island

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

    Đầu vào 

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

    Đầu ra 

    6