洛谷 P1596：Lake Counting S ← Flood fill
【题目来源】
https://www.acwing.com/problem/content/1099/
https://oj.czos.cn/p/1435
【题目描述】
由于最近的降雨，水在农夫约翰的田地里积聚了。田地可以表示为一个 N×M 的矩形（1≤N≤100，1≤M≤100）。每个方格中要么是水（W），要么是干地（.）。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的，其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图，确定他有多少个水塘。
【输入格式】
第 1 行：两个用空格分隔的整数 N 和 M。
第 2 行到第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。
每个字符要么是 W，要么是 .。
字符之间没有空格。
【输出格式】
第 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.
【输出样例】
3
【数据范围】
1≤N,M≤100
【算法分析】
● 泛洪算法（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=1e2+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(tx>=0 && ty>=0 && tx<n && ty<m && 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+pair】
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e2+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;
q.push({x,y});
mp[x][y]='.';
while(!q.empty()) {
PII t=q.front();
q.pop();
for(int i=0; i<8; i++) {
int tx=t.first+dx[i];
int ty=t.second+dy[i];
if(tx>=0 && ty>=0 && tx<n && ty<m && mp[tx][ty]=='W') {
mp[tx][ty]='.';
q.push({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') {
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
*/【算法代码三：bfs+结构体】
#include<bits/stdc++.h>
using namespace std;
struct PII {
int u;
int v;
} pos;
const int N=1e2+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
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158655296
https://www.acwing.com/solution/content/130658/
https://blog.csdn.net/qq_52156445/article/details/117133513
https://blog.csdn.net/Jay_fearless/article/details/107947462
浙公网安备 33010602011771号