1.自然语言描述 面对一个二维平面图，图中元素有不同的种类，问题要求出图中所有某一种类的元素构成了多少连通块？最大连通块的大小是多少？或是满足特殊要求的连通块有多少个？……这些问题，他们的输入数据规模往往不大；绕不开连通块这个话题。
Flood fill算法能够求出图中要求的连通块：模拟用水（想象一下Minecraft中岩浆桶和水桶的作用效果）灌满一个连通块；灌满图中所有连通块的次数就是连通块的个数。Flood fill算法在遍历连通块时采用的是BFS策略。
2.代码描述 题目：Acwing 1097.池塘计数 题目链接
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int MAXN=1010; int n,m; char s[MAXN][MAXN]; bool st[MAXN][MAXN]; //flood fill是一种基于BFS的算法,它通过对每一个状态进行BFS,从而找到与当前点连通的连通分量,进而找到所有连通分量 //像洪水从一个点灌入,看它最多能漫到哪些点 void bfs(int sx,int sy) { queue<PII> q; q.push({sx,sy}); st[sx][sy]=true; while(!q.empty()){ PII t=q.front(); q.pop(); for(int i=t.x-1;i<=t.x+1;i++) for(int j=t.y-1;j<=t.y+1;j++){ if(i<0||i>=n|j<0||j>=m) continue; if(!st[i][j]&&s[i][j]=='W'){ q.push({i,j}); st[i][j]=true; } } } } int main(void) { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>s[i][j]; int ans=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(!st[i][j]&&s[i][j]=='W'){ bfs(i,j); ans++; } cout<<ans<<endl; return 0; }题目：Acwing 1098.城堡问题 题目链接
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef pair<int,int> PII; const int MAXN=55; int n,m; int dx[]={0,-1,0,1},dy[]={-1,0,1,0}; int g[MAXN][MAXN]; bool st[MAXN][MAXN]; int bfs(int sx,int sy) { queue<PII> q; q.push({sx,sy}); int area=0; while(!q.empty()){ PII t=q.front(); q.pop(); int x=t.first,y=t.second; if(st[x][y]) continue; st[x][y]=true; area++; for(int i=0;i<4;i++){ int nx=x+dx[i],ny=y+dy[i]; if(!st[nx][ny]&&!(g[x][y]>>i&1)) q.push({nx,ny}); } } return area; } int main(void) { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>g[i][j]; int ans=0,cnt=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(!st[i][j]){ cnt++; ans=max(ans,bfs(i,j)); } cout<<cnt<<endl<<ans<<endl; return 0; }题目：Acwing 1106.山峰问题 题目链接
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef pair<int,int> PII; const int MAXN=1010; int g[MAXN][MAXN]; bool st[MAXN][MAXN]; int n; void bfs(int sx,int sy,bool &has_h,bool &has_l) { queue<PII> q; q.push({sx,sy}); while(!q.empty()){ PII t=q.front(); q.pop(); int x=t.first,y=t.second; if(st[x][y]) continue; st[x][y]=true; for(int i=x-1;i<=x+1;i++) for(int j=y-1;j<=y+1;j++){ if(i<0||i>=n||j<0||j>=n) continue; if(g[i][j]!=g[x][y]){ if(g[i][j]>g[x][y]) has_h=true;//发现比当前山脉高的山 else has_l=true; }else if(!st[i][j]) q.push({i,j}); } } } int main(void) { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>g[i][j]; int peak,valley; peak=valley=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(!st[i][j]){ bool has_h,has_l; has_h=has_l=false; bfs(i,j,has_h,has_l);//沿着当前山脉遍历 if(!has_h) peak++;//没有比当前山脉更高的山，所以当前山脉为山峰 if(!has_l) valley++;//反之则为山谷 } cout<<peak<<' '<<valley<<endl; return 0; }