【题解】【bfs】T1249 Lake Counting

#include<bits/stdc++.h>
#define N 105
using namespace std;
//方向数组
int d[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}} ;
struct point{
	int x,y;
};
char a[N][N];//地图 
int vis[N][N],m,n,ans;//走没走过
queue<point> que; 
void bfs(int x,int y){
	vis[x][y]=1;
	point nw;
	nw.x=x;
	nw.y=y;
	que.push(nw);
	while(!que.empty()){
		point nwq=que.front();
		for(int i=0;i<8;i++){
			int nx=nwq.x+d[i][0];
			int ny=nwq.y+d[i][1];
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='W'&&!vis[nx][ny]){
				//入队 标记走过
				point nxq;
				nxq.x=nx;
				nxq.y=ny;
				que.push(nxq);
				vis[nx][ny]=1; 
			}
		}
		que.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]=='W'&&!vis[i][j]){
				//开始搜索 积水+1
				bfs(i,j);
				ans++; 
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}