用 Python 编写程序来计算给定矩阵中的岛屿数量
pythonserver side programmingprogramming更新于 2026/2/2 3:24:17
假设我们有一个二进制矩阵，我们必须找出矩阵中的岛屿数量。这里 1 表示陆地，0 表示水，所以岛屿是一组相邻的 1，其周边被水包围。这里我们认为邻居只能是水平或垂直的，而不是对角线的。
所以，如果输入如下
| 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 0 | |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
则输出为 4。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 explore() 。这将获取行、列、矩阵
- 如果行和列不在矩阵范围内或矩阵[行，列]为 0，则
- 返回
- matrix[row, col] := 0
- explore(row + 1, col, matrix)
- explore(row - 1, col, matrix)
- explore(row, col + 1, matrix)
- explore(row, col - 1, matrix)
- 从主方法，执行以下操作 −
- 如果矩阵为空，则
- 返回 0
- islands := 0
- 对于范围从 0 到矩阵行数的行，执行
- 对于范围从 0 到矩阵列数的 col，执行
- 如果 matrix[row, col] 与 1 相同，则
- islands := islands + 1
- explore(row, col, matrix)
- 如果 matrix[row, col] 与 1 相同，则
- 对于范围从 0 到矩阵列数的 col，执行
- 返回 islands
让我们看看下面的实现以便更好地理解 −
示例
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))
输入
[ [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] ]
输出
4
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
