作者的话:
感觉不如深度优先搜索()表达能力不行,我讲的可能不太明白。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
分析
题意
> 题目:有一块 N×MN×MN×M 的土地,雨后积起了水,有水标记为‘W’,干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼。
实际上,这道题目是一道典型的“连通块”类型题目,即在全图查找四个方向或八个方向上相互连通的节点。一般来说,我们用深度优先搜索(dfs)和广度优先搜索(bfs)去做这类题。
思路
这题我采用了广度优先搜索。
我们需要循环遍历整块土地,当遇到有水的土地(即‘W’)时,往它的右、右下、下、左下、左、左上、上、右上这八个方向去继续查找有水的土地,然后一直循环直到全部都找出来。
用一般的话说,就是将第一个有水的位置压入队列,然后while循环每次取队首,去八方向循环尝试,如果还有的话就将新的位置填充为干燥的土地(即‘.’),然后把新的压入队列。每次结束查找后就将计数变量+1,最后输出计数变量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2024年09月08日 版本1