洪水填充

洪水填充算法（flood fill algorithm），也称为泛洪算法，用于将格点的某一个连通区域内的所有格点状态修改为目标状态，状态往往用颜色表示。一般的处理方法是，从一个起始点开始把附近与其连通的点填充成新的颜色，直到连通区域内的所有点都被处理过为止，因为其思路类似洪水从一个区域扩散到所有能到达的其他区域而得名。

DFS、BFS 都可以用来实现洪水填充算法，常见的邻域包括四邻域和八邻域等。

例题：P1596 [USACO10OCT] Lake Counting S

1. 存储网格图
   f[x][y] 存储网格图
   dx[8] dy[8] 存储方向偏移量
2. 搜索
   枚举单元格，判断是否可以进入
   如果可以进入，则水坑数量+1，并且将该单元格所属水坑的其他单元格全都进入一遍（这里DFS和BFS都可实现，两种实现的时间复杂度都为 \(O(nm)\)）
   为避免重复搜索，对走过的单元格进行标记

参考代码（DFS 实现）

#include <cstdio>
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y) {
    f[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
            dfs(xx, yy);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", f[i]);
    int lake = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            if (f[i][j] == 'W') {
                lake++;
                dfs(i, j);
            }
    printf("%d\n", lake);
    return 0;
}

参考代码（BFS 实现）

#include <cstdio>
#include <queue>
using namespace std;
char f[105][105];
int n, m;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node {
    int x, y;
};
void bfs(int x, int y) {
    f[x][y] = '.';
    queue<Node> q;
    q.push({x, y});
    while (!q.empty()) {
        Node t = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && f[xx][yy] == 'W') {
                f[xx][yy] = '.';
                q.push({xx, yy});
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", f[i]);
    int lake = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            if (f[i][j] == 'W') {
                lake++;
                bfs(i, j);
            }
    printf("%d\n", lake);
    return 0;
}