【题目来源】
【题目描述】
农夫约翰有一片 N∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
【输入格式】
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含 M 个字符，字符为”W”或”·”，用以表示矩形土地的积水状况，字符之间没有空格。
【输出格式】
输出一个整数，表示池塘数目。
【输入样例】
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
【输出样例】
3
【数据范围】
1≤N,M≤1000
【算法分析】
● 泛洪算法（Flood fill）是一种针对 “连通区域” 的处理思想。核心逻辑是：从一个起始点出发，像洪水扩散一样，遍历所有 “相邻且满足相同条件” 的结点（比如同颜色、同数值），并对这些结点进行标记、修改或计数。泛洪算法（Flood fill）常用于从棋盘模型的某个点出发，然后扩展到与这个点相邻的上、下、左、右、左上、右上、左下、右下等八个点。
● 典型场景：画图软件里的「油漆桶工具」—— 点击一个红色像素，所有和它连通的红色像素都会被换成蓝色，这个过程就是 Flood fill。
● Flood Fill 是一类 “连通区域填充” 的问题场景 / 算法思想，用 BFS/DFS 都可以实现。但 BFS 是实现 Flood Fill 最常用的核心算法之一。 原因在于，BFS “无栈溢出风险 + 天然支持层级 / 距离计算”，适配 Flood fill 的大多数实际场景。DFS 仅在小网格、无层级需求时更简洁，但稳定性不如 BFS。
【算法代码一：dfs】
#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
char mp[N][N];
int dx[]= {1,1,0,-1,-1,-1,0,1};
int dy[]= {0,1,1,1,0,-1,-1,-1};
int n,m,ans;void dfs(int x,int y) {/*Mark the current position as '.'to indicate that it has been visited,in order to avoid redundant processing.*/mp[x][y]='.';for(int i=0; i<8; i++) {int tx=x+dx[i];int ty=y+dy[i];if(mp[tx][ty]=='W') {dfs(tx,ty);}}
}int main() {cin>>n>>m;for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {cin>>mp[i][j];}}for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {if(mp[i][j]=='W') {dfs(i,j);ans++;}}}cout<<ans<<endl;return 0;
}/*
in:
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.out:
3
*/【算法代码二：bfs】
#include<bits/stdc++.h>
using namespace std;struct PII {int u;int v;
} pos;const int N=1e3+5;
char mp[N][N];
int dx[]= {1,1,0,-1,-1,-1,0,1};
int dy[]= {0,1,1,1,0,-1,-1,-1};
int n,m,ans;void bfs(int x,int y) {queue<PII> q;pos.u=x, pos.v=y;q.push(pos);while(q.size()) {PII t=q.front();q.pop();for(int i=0; i<8; i++) {int tx=t.u+dx[i],ty=t.v+dy[i];if(tx<0 || ty<0 || tx>=n || ty>=m) continue;if(mp[tx][ty]=='.') continue;mp[tx][ty]='.';pos.u=tx, pos.v=ty;q.push(pos);}}
}int main() {cin>>n>>m;for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {cin>>mp[i][j];}}for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {if(mp[i][j]=='W') {bfs(i,j);ans++;}}}cout<<ans<<endl;return 0;
}/*
in:
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.out:
3
*/
【参考文献】