搜索算法（算法竞赛、蓝桥杯）--DFS与BFS水坑计数（洪水覆盖问题）_池塘问题bfs洛谷

1、B站视频链接：B10 DFS 水坑计数_哔哩哔哩_bilibili

题目链接：[USACO10OCT] Lake Counting S - 洛谷

#include <bits/stdc++.h>
using namespace std;
 
const int N=1010;
int n,m;
char g[N][N];
int dx[8]={-1,-1,-1,0,1,1,1,0};//注意把方向探照灯的细节 
int dy[8]={-1,0,1,1,1,0,-1,-1};
 
void dfs(int x,int y){
	g[x][y]='.';//搜到'W'的地方全部变成'.'标记判重 
	for(int i=0;i<8;i++){
		int a=x+dx[i],b=y+dy[i];
		if(a<0||a>=n||b<0||b>=m)continue;
		if(g[a][b]=='.')continue;
		dfs(a,b);
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		scanf("%s",g[i]);//逐行读入字符串 
	}
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='W'){
				ans++,dfs(i,j);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

2、用BFS解决问题