英文原文
You have an integer matrix representing a plot of land, where the value at that location represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix.
Example:
Input: [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1] ] Output: [1,2,4]
Note:
0 < len(land) <= 10000 < len(land[i]) <= 1000
中文题目
你有一个用于表示一片土地的整数矩阵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
通过代码
高赞题解
⏲阅读大约需要 6min
🔑解题思路
依旧是 BFS 模板题。
这一次总结一下 BFS 的几个主要步骤
- 肯定会用到 deque 的结构用来模拟队列，BFS精髓也在这里。
- 队列里肯定是有一个初始点
- 然后每次处理从队列中出队一个元素
- 对元素进行扩张(具体如何扩张需要根据题目要求，一般是上下左右四个方向，本题是算上斜向共8个方向)
- 对于扩张后满足某条件的点再进行处理，根据需要进入队列，进入队列的点就是扩到下一层的点(不同题目需要处理的方法不同，大家灵活运用)
- 然后接着循环处理 deque 中的元素，直到 deque 为空，则代表所有点都已经完成扩张
- 最后根据题目要求输出结果(当然这已经不属于 BFS 模板的范围了)
所有 BFS 的模板题都大致是这个思路，只不过是可能有小的变形。
最重要的还是要培养自己辨识某题是 BFS 的能力和敏感度，还有就是要明确要从那些点开始扩张，搞清楚这两点再加上 BFS 模板，这类题就问题不大了。
🔶类似题目
下面 3 题是最近每日一题中出现的 BFS 模板题，还不太熟悉 BFS 的小伙伴可以看一下往期的视频和文字题解
面试题13. 机器人的运动范围
面试题13. 机器人的运动范围的视频题解
🐼代码部分
class Solution:
def pondSizes(self, land: List[List[int]]) -> List[int]:
res = []
for row in range(len(land)):
for col in range(len(land[0])):
if land[row][col] == 0:
tmp = collections.deque()
tmp_count = 1
land[row][col] = -1 # 将访问的点标记进行标记
tmp.append([row, col])
while len(tmp) > 0:
x, y = tmp.popleft()
# 注意题目要求，斜向也要算，所以一共是 8 个方向
for new_x, new_y in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1],
[x - 1, y - 1], [x - 1, y + 1], [x + 1, y + 1], [x + 1, y - 1]]:
if 0 <= new_x < len(land) and 0 <= new_y < len(land[0]) and land[new_x][new_y] == 0:
tmp_count += 1
land[new_x][new_y] = -1
tmp.append([new_x, new_y])
res.append(tmp_count)
return sorted(res)如果你喜欢这条题解的话，欢迎点赞👍👍👍
之前的一些文字版题解和视频版题解也可以在下面的链接中找到，欢迎关注！
- 文字版题解：【莲子熊猫_力扣主页】
- 视频版题解：【熊猫刷题_b站】 【熊猫刷题_油管】
最后，欢迎加入@fuxuemingzhu大佬创建的每日一题打卡网站＆微信打卡群，你将收获：
- 一群志同道合的小伙伴：与 500+ 位优秀的小伙伴督促打卡，收获新知，共同进步
- 和刷题大佬们一起玩耍：负雪明烛@fuxuemingzhu、wei哥@liweiwei1419、甜姨@sweetiee都在群里
就差你了，赶快加入，一起来玩耍吧！👉https://ojeveryday.com/
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 21081 | 34354 | 61.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
