面试题 16.19. 水域大小

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]
提示：

• 0 < len(land) <= 1000
• 0 < len(land[i]) <= 1000

Python 解答：
1.BFS

class Solution:
    def pondSizes(self, land: List[List[int]]) -> List[int]:
        res = []
        length = len(land)
        width = len(land[0])
        flag = [[1 for i in range(width)] for j in range(length)]
        for i in range(length):
            print(land[i])
        for i in range(length):
            for j in range(width):
                if flag[i][j] and land[i][j] == 0:
                    area = 0
                    temp = [[i,j]]
                    while temp:
                        x, y = temp.pop(0)
                        if flag[x][y] and land[x][y] == 0:
                            area += 1
                            flag[x][y] = 0
                        if x-1 >= 0 and y-1 >= 0 and flag[x-1][y-1] and land[x-1][y-1] == 0:
                            temp.append([x-1, y-1])
                        if x-1 >= 0 and flag[x-1][y] and land[x-1][y] == 0:
                            temp.append([x-1, y])
                        if x-1 >= 0 and y+1 < width and flag[x-1][y+1] and land[x-1][y+1] == 0:
                            temp.append([x-1, y+1])
                        if y-1 >= 0 and flag[x][y-1] and land[x][y-1] == 0:
                            temp.append([x, y-1])
                        if y+1 < width and flag[x][y+1] and land[x][y+1] == 0:
                            temp.append([x, y+1])
                        if x+1 < length and y-1 >= 0 and flag[x+1][y-1] and land[x+1][y-1] == 0:
                            temp.append([x+1, y-1])
                        if x+1 < length and flag[x+1][y] and land[x+1][y] == 0:
                            temp.append([x+1, y])
                        if x+1 < length and y+1 < width and flag[x+1][y+1] and land[x+1][y+1] == 0:
                            temp.append([x+1, y+1])
                    res.append(area)
        res.sort()
        return res