难度: Medium
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
示例：
输入： [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1] ] 输出： [1,2,4]
提示：
0 < len(land) <= 10000 < len(land[i]) <= 1000运行时间: 108 ms
内存: 25.4 MB
class Solution:
def pondSizes(self, land: List[List[int]]) -> List[int]:
res = []
m = len(land)
n = len(land[0])
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >= n or land[x][y] != 0: return 0
land[x][y] = 1
return dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1) + dfs(x-1, y-1) + dfs(x-1, y+1) + dfs(x+1, y-1) + dfs(x+1, y+1) + 1
for i in range(m):
for j in range(n):
if land[i][j] != 0: continue
res.append(dfs(i, j))
res.sort()
return res
题解采用深度优先搜索(DFS)的方法来解决问题。首先遍历矩阵中的每个元素，当找到一个值为0的元素时，即水域的起始位置，从这个点开始进行DFS以探索整个相连的水域区域。DFS探索包括向八个方向扩展（上、下、左、右以及四个对角方向），并将访问过的水域标记为1以避免重复计算。每次调用DFS时，如果它是水域，则大小增加1，并递归计算所有相邻的水域大小，然后将结果累加。最终，每次从一个未标记的水域开始的DFS会得到一个完整池塘的大小，并将其添加到结果列表中。遍历完成后，将列表中的池塘大小进行排序并返回。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def pondSizes(self, land: List[List[int]]) -> List[int]:
res = [] # 存放所有池塘的大小
m = len(land) # 矩阵的行数
n = len(land[0]) # 矩阵的列数
def dfs(x, y):
# 边界条件检查
if x < 0 or x >= m or y < 0 or y >= n or land[x][y] != 0: return 0
land[x][y] = 1 # 标记当前水域已访问
# 递归调用8个方向并累加池塘大小，包括当前点
return dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1) + dfs(x-1, y-1) + dfs(x-1, y+1) + dfs(x+1, y-1) + dfs(x+1, y+1) + 1
for i in range(m):
for j in range(n):
if land[i][j] != 0: continue # 只在水域起始位置开始DFS
res.append(dfs(i, j)) # 计算并收集当前池塘大小
res.sort() # 排序池塘大小
return res
在处理连通区域问题时，DFS和BFS都是可行的方法。选择DFS的原因通常是因为其实现相对简单，尤其是在递归形式下，代码更加直观易懂。DFS通常占用的额外空间少于BFS，因为它的空间复杂度主要由递归深度决定，而BFS需要存储整个层级的节点，尤其是在最坏情况下，可能需要更多的内存来存储队列。此外，在连通区域的探索中，DFS可以更快地达到深层次的节点，这在某些情况下可能更为高效。
将访问过的水域标记为1确实会改变原始矩阵，这在某些情况下可能会影响算法的重用性或者测试的便利性。例如，如果需要对同一个矩阵多次计算或进行后续处理，这种修改会造成原始数据丢失。解决这一问题的方法包括使用一个同样大小的标记数组来记录访问状态，这样可以避免修改原始数据。这种方法虽然增加了空间复杂度，但保持了数据的完整性，便于重用和测试。
这个边界条件检查确保了在DFS过程中不会发生数组越界，并且能够避免重复访问已经标记过的水域。通过检查索引是否超出矩阵的边界和当前位置的值是否为0，我们可以确保每次递归调用都是安全的且只处理未被访问的水域。这是一种有效的方式来保证程序的稳定性和正确性。