[数据结构与算法]AcWing 1097 池塘计数 题解（BFS—连通块—Flood Fill）

AcWing 1097 池塘计数
连通块问题，Flood Fill（洪水覆盖）算法，很经典的宽搜，注意细节即可

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

#define x first
#define y second

typedef pair<int, int>PII;

int n, m;
int ans;
PII q[N * N];
char g[N][N];
bool st[N][N];

void bfs(int sx, int sy){
	st[sx][sy] = true;
	int hh = 0, tt = 0;
	q[0] = {sx, sy};
	
	while(hh <= tt){
		PII t = q[hh ++ ];
		for(int i = t.x - 1; i <= t.x + 1; i ++ ){
			for(int j = t.y - 1; j <= t.y + 1; j ++ ){
				if(i == t.x && j == t.y) continue;
				if(i < 0 || i >= n || j < 0 || j >= m || g[i][j] == '.' || st[i][j]) continue;
				
				q[ ++ tt] = {i, j};
				st[i][j] = true;
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i = 0; i < n; i ++ ){
		for(int j = 0; j < m; j ++ ){
			cin>>g[i][j];
		}
	}
	
	for(int i = 0; i < n; i ++ ){
		for(int j = 0; j < m; j ++ ){
			if(g[i][j] == 'W' && !st[i][j]){
				bfs(i, j);
				ans ++ ;
			}
		}
	}
	
	cout<<ans<<endl;
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖