在Python矩阵中查找最大岛屿面积的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个二进制矩阵。在这里1代表土地，0代表水，而岛屿是1的一组，它们相邻，周围被水包围。我们可以假设矩阵的边缘被水包围。我们必须找到矩阵中最大的岛屿的面积。

所以，如果输入像

0011111
0000000
0111100
0011000
0000011
0000010

那么输出将为6。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个功能dfs()。这将采用矩阵r，c

  • 总计：=总计+ 1

  • 矩阵[r，c]：= 0

  • 如果r-1> = 0并且matrix [r-1，c]与1相同，则

    • dfs（矩阵，r-1，c）

  • 如果c-1> = 0并且matrix [r，c-1]与1相同，则

    • dfs（矩阵，r，c-1）

  • 如果r + 1 <r_len并且matrix [r + 1，c]与1相同，则

    • dfs（矩阵，r + 1，c）

  • 如果c + 1 <c_len并且matrix [r，c + 1]与1相同，则

    • dfs（矩阵，r，c +1）

  • 从主要方法中，执行以下操作-

  • r_len：=矩阵的行数

  • c_len：=矩阵的列数

  • max_island：= 0

  • 对于0到r_len-1范围内的r

    • 如果matrix [r，c]与1相同，则

    • 总计：= 0

    • dfs(matrix,r,c)

    • max_island：= max_island的最大值，总计

    • 对于0到c_len-1范围内的c

    • 返回max_island

    让我们看下面的实现以更好地理解-

    示例

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

    输入项

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

    输出结果

    6

    以上是 在Python矩阵中查找最大岛屿面积的程序 的全部内容， 来源链接： utcz.com/z/353394.html

    回到顶部