你有一个用于表示一片海洋的整数矩阵,该矩阵中每个点的值代表对应地点的海水深度。若值为0则表示陆地。由垂直、水平或对角连接的陆地为岛屿。岛屿的大小是指相连接的陆地的个数。编写一个方法来计算矩阵中所有岛屿的大小,返回值需要从小到大排序。
时间: 2024-11-10 07:13:44 浏览: 19
你可以通过广度优先搜索(BFS)算法来解决这个问题。以下是步骤:
1. 首先,初始化一个队列用于存储待访问的节点,以及一个集合用于存储已经访问过的陆地标记。将矩阵中的每一个值为0(陆地)的位置加入队列。
2. 然后进入循环,直到队列为空:
a. 从队列中取出第一个位置(x, y),并标记为已访问。
b. 检查周围上下左右四个相邻位置(x+1, y),(x-1, y), (x, y+1), (x, y-1)。如果它们也是0并且未被访问过,就将它们添加到队列,并增加当前岛的大小(可以使用计数器)。
3. 当队列遍历完后,岛屿的大小就是之前记录的大小列表。
4. 最后,你需要对所有岛屿的大小进行排序。你可以选择使用Python的`sorted()`函数,传入一个匿名函数作为key,这个函数比较岛屿的大小。排序完成后,返回排序后的岛屿大小列表。
这里是一个伪代码示例:
```python
def island_sizes(matrix):
rows, cols = len(matrix), len(matrix[0])
visited = set()
queue = [(i, j) for i in range(rows) for j in range(cols) if matrix[i][j] == 0]
def is_valid(i, j):
return 0 <= i < rows and 0 <= j < cols and matrix[i][j] == 0 and (i, j) not in visited
def dfs(i, j):
matrix[i][j] = -1
visited.add((i, j))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dx, dy in directions:
nx, ny = i + dx, j + dy
if is_valid(nx, ny):
dfs(nx, ny)
island_sizes = []
while queue:
island_size = 1
node = queue.pop(0)
dfs(node[0], node[1])
# 增加岛屿大小统计
for x, y in visited:
island_size += matrix[x][y] == 0
island_sizes.append(island_size)
visited.clear()
# 返回排序后的岛屿大小列表
return sorted(island_sizes)
# 使用示例
matrix = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]]
print(island_sizes(matrix)) # 输出:[1, 1, 2, 3]
```
阅读全文