（算法竞赛）DFS深搜3——数池塘问题解析与代码实现
题目描述
农夫约翰的农场可以表示成 N×M 个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（
W），或者没有积水（.）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。
输入
第 1 行：由空格隔开的两个整数 N 和 M。
第 2 到 N+1 行：每行 M 个字符代表约翰农场的一排方格的状态。每个字符或者是
W或者是.，字符之间没有空格。数据范围
1≤N,M≤100
输出
输出只有 1 行，输出约翰农场上的池塘数。
样例
输入
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.输出
13来源
深搜 递归
问题分析
-
问题本质：
-
这是一个典型的连通块计数问题，可以通过深度优先搜索（DFS）或广度优先搜索（BFS）解决。
-
每个连通的积水区域（池塘）可以通过搜索算法标记并计数。
-
-
关键点：
-
使用二维数组存储网格状态。
-
使用一个访问标记数组（
vis）记录每个格子是否被访问过，避免重复搜索。 -
通过递归实现DFS，搜索每个积水格子的上下左右四个方向。
-
-
搜索方向：
-
定义方向数组
dx和dy，分别表示四个方向（右、左、下、上）的行和列变化。
-
代码解析
以下是基于DFS的Python代码实现及其详细解析：
def dfs(xx, yy):
"""
深度优先搜索函数，用于标记一个池塘中的所有积水格子。
:param xx: 当前行
:param yy: 当前列
"""
vis[xx][yy] = 1 # 标记当前格子为已访问
for i in range(4): # 遍历四个方向
x, y = xx + dx[i], yy + dy[i] # 计算相邻格子的坐标
# 检查是否在网格范围内、未访问且为积水格子
if 0 <= x < n and 0 <= y < m and not vis[x][y] and a[x][y] == 'W':
dfs(x, y) # 递归搜索相邻格子
# 输入网格的行数和列数
n, m = map(int, input().split())
# 输入网格状态
a = [input() for _ in range(n)]
# 初始化访问标记数组
vis = [[0] * m for _ in range(n)]
# 定义方向数组
dx = [0, 0, 1, -1] # 行变化（右、左、下、上）
dy = [1, -1, 0, 0] # 列变化
# 初始化池塘计数
ans = 0
# 遍历每个格子
for i in range(n):
for j in range(m):
# 如果当前格子未访问且为积水格子
if not vis[i][j] and a[i][j] == 'W':
ans += 1 # 发现一个新池塘
dfs(i, j) # 标记整个池塘
# 输出池塘数量
print(ans)代码运行逻辑
-
输入网格状态：
-
使用
input()逐行读取网格状态，存储到二维列表a中。
-
-
初始化访问标记数组：
-
创建一个与网格大小相同的二维数组
vis，初始值为0，用于记录每个格子是否被访问过。
-
-
DFS函数：
-
标记当前格子为已访问。
-
遍历四个方向，计算相邻格子的坐标。
-
如果相邻格子在网格范围内、未访问且为积水格子，则递归调用
dfs。
-
-
遍历网格：
-
遍历每个格子，如果当前格子未访问且为积水格子，则发现一个新池塘，并调用
dfs标记整个池塘。
-
-
输出结果：
-
输出池塘的总数。
-
运行结果示例
输入：
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.输出：
13
解释：
-
网格中共有13个连通的积水区域（池塘）。
-
每个池塘通过DFS被标记并计数。
总结
这道题考察了深度优先搜索（DFS）的应用，适用于解决连通块计数问题。通过递归实现DFS，可以高效地标记每个池塘中的所有积水格子，并统计池塘的数量。希望这篇文章能帮助你更好地理解和解决类似问题。