你有一个用于表示一片土地的整数矩阵 land,该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。 池塘的大小是指相连接的水域的个数。 编写一个方法来计算矩阵中所有池塘的大小,返回值需要从小到大排序。 示例: 输入: [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1] ] 输出: [1,2,4]
时间: 2023-09-26 16:13:56 浏览: 39
好的,这是一道计算矩阵中池塘大小的问题,我可以为您提供代码实现。以下是 Python 代码实现:
```python
from typing import List
def pondSizes(land: List[List[int]]) -> List[int]:
m, n = len(land), len(land[0])
res = []
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or land[i][j] != 0:
return 0
land[i][j] = -1
return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1) + dfs(i+1, j+1) + dfs(i-1, j-1) + dfs(i+1, j-1) + dfs(i-1, j+1)
for i in range(m):
for j in range(n):
if land[i][j] == 0:
size = dfs(i, j)
res.append(size)
return sorted(res)
```
这段代码中,我们使用了 DFS 算法来搜索每个池塘的大小。具体实现是,从每个为 0 的格子开始进行 DFS,统计相连的格子数量,即为该池塘的大小。在 DFS 过程中,我们需要判断边界条件和格子是否已经被访问过。
最终返回的是池塘大小的排序结果。您可以用上述代码进行测试,看看是否符合您的要求。