种子填充（Floodfill） 算法： 从任意 W 开始，不停地把邻接的 W 用 . 代替。1 次 DFS 后与初始 W 连接的所有 W 都被替换成 . 了。 因此，直到图中不存在 W 为止，总共进行 DFS 的次数就是答案了。

问题：

有一个大小为 N x M 的园子，雨后积水。
8 连通的积水被认为是连接在一起的，
请求出园子里一共有多少水洼？
8 连通指的是下图中相对 W 的 * 的部分：

***
*W*
***

限制条件： N，M <= 100
洛谷 : P1596

代码：

#include <iostream>
using namespace std;

#define MAXN 100
#define MAXM 100

int n, m;
char filed[MAXN+2][MAXM+2];

void dfs(int x, int y) {
    filed[x][y] = '.'; // 标记当前点为已访问
    
    // 遍历八个方向
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            int nx = x + dx, ny = y + dy;
            // 检查边界和是否为'W'
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && filed[nx][ny] == 'W') {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> filed[i][j];
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) { // 修正列遍历范围为1到m
            if (filed[i][j] == 'W') {
                dfs(i, j);
                res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

代码解析

1. 数据结构：二维数组 filed 存储园子状态，有效索引为 1 到 n 和 1 到 m。
2. DFS函数：将当前水洼位置标记为 .，递归处理八个方向的相邻点，确保所有连通区域被标记。
3. 主函数：
   • 输入处理：正确读取 n 行 m 列数据。
   • 遍历所有位置，遇到 W 时进行DFS并计数，每次DFS标记一个独立水洼。

复杂度

• 时间复杂度：O(N*M)，每个点最多访问一次。
• 空间复杂度：O(NM)，递归栈深度最差情况下为O(NM)。

修正后的代码能正确统计八连通水洼数量，符合题目要求。

模板：

int n, m; // 输入
char filed[MAXN+2][MAXM+2];

// 现在位置（x,y)
void dfs(int x, int y) {
    filed[x][y] = '.'; // 将现在位置替换为.
  
  // 循环遍历可以移动的 8 个方向
  for (int dx = -1; dx <= 1; dx++)
    for (int dy = -1; dy <= 1; dy++) {
      // 向 x 方向移动 dx，向 y 方向移动 dy
      int nx = x + dx, ny = y + dy;
      // 判断（dx，dy）是否在园子内，是否有积水
      if (1<=nx&&nx<=n && 1<=ny&&ny<=m && filed[nx][ny]=='W')
        dfs(nx,ny);
    }
  return;
}
int res = 0; // 初始有 0 个水洼
for (int i = 1; i <= n; i++)
  for (int j = 0; j <= m; j++)
    if (filed[i][j] == 'W')
      dfs(i,j), res++;
cout << res << endl;

感谢支持