HJ149 数水坑

题目描述

由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个 N×M 的矩形网格，每个格子要么是水 W，要么是干地 .。

若两个水格子在八连通（上下左右及四条对角线）意义下互达，则它们属于同一个水坑。

给出田地示意图，计算水坑数量。

解题思路

这是一道经典的 Flood Fill（洪水填充） 问题，本质是求连通分量个数。

核心思路

1. 遍历网格：逐个扫描每个格子
2. 发现新水坑：遇到未访问的 W 时，计数器 +1
3. 标记整个水坑：用 DFS 将该 W 及其所有八连通的 W 标记为已访问
4. 继续遍历：寻找下一个未访问的 W

八连通方向

  ← ↖ ↑ ↗ →
↙ ↓ ↘

共 8 个方向：(±1, ±1) 和 (±1, 0) 和 (0, ±1)

代码实现

n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]

visited = [[False] * m for _ in range(n)]

def dfs(x, y):
    visited[x][y] = True
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if dx == 0 and dy == 0:
                continue
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == 'W':
                dfs(nx, ny)

count = 0
for i in range(n):
    for j in range(m):
        if not visited[i][j] and grid[i][j] == 'W':
            dfs(i, j)
            count += 1

print(count)

代码解析

核心函数 dfs(x, y)

作用：将 (x, y) 所属的整个水坑标记为已访问

def dfs(x, y):
    visited[x][y] = True  # 标记当前格子
    # 遍历 8 个方向
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if dx == 0 and dy == 0:  # 跳过自己
                continue
            nx, ny = x + dx, y + dy
            # 边界检查 + 未访问 + 是水
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == 'W':
                dfs(nx, ny)

算法流程

遍历网格：
(0,0)是'W'且未访问 → count=1, DFS标记整个水坑
(0,1)是'.' → 跳过
(0,2)是'W'且未访问 → count=2, DFS标记整个水坑
...

示例演示

输入：

W........WW.
.WWW.....WWW
....WW...WW.

过程：

第1个水坑: (0,0) → 只有这一个，count=1
第2个水坑: (1,1) → (1,2) → (1,3)，count=2
第3个水坑: (0,9) → (0,10) → (1,10) → (2,10)，count=3
...

输出：3

关键点

1. 八连通：注意对角线也要考虑，用双重循环 dx, dy in [-1, 0, 1]
2. 跳过自身：if dx == 0 and dy == 0: continue
3. visited 标记：防止重复访问，确保每个水坑只计数一次

复杂度分析

• 时间复杂度：O(N × M) - 每个格子最多访问一次
• 空间复杂度：O(N × M) - visited 数组 + 递归栈深度

变种问题

问题	修改点
求最大水坑面积	DFS 时返回该连通块的大小
四连通水坑	方向数组改为上下左右 4 个方向
BFS 解法	用队列代替递归，避免栈溢出
并查集解法	将相连的水坑合并到同一个集合

优化建议

1. 原地标记：直接把访问过的 W 改为 .，省去 visited 数组
2. BFS 避免爆栈：对于极大网格，BFS 更安全
3. 并查集：适合需要频繁合并/查询的场景

# 原地标记优化版
def dfs(x, y):
    grid[x][y] = '.'  # 直接改为干地
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if dx == 0 and dy == 0:
                continue
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 'W':
                dfs(nx, ny)