对于flood-fill问题不用考虑用dfs还是bfs,都要走完的
dfs
#include<bits/stdc++.h>
using namespace std;
char a[1010][1010];
int tx[8]={-1,1,0,0,-1,-1,1,1},ty[8]={0,0,-1,1,-1,1,-1,1};
void dfs(int x,int y){
a[x][y]='.';
for(int i=0;i<8;i++){
if(a[x+tx[i]][y+ty[i]]=='W'){
dfs(x+tx[i],y+ty[i]);
}
}
return;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
bfs
#include<bits/stdc++.h>
using namespace std;
char a[1010][1010];
int dx[8]={1,-1,0,0,1,1,-1,-1},dy[8]={0,0,1,-1,1,-1,1,-1},ans;
void bfs(int x,int y){
queue<pair<int,int> >que;
que.push(make_pair(x,y));
while(!que.empty()){
pair<int,int>now=que.front();
que.pop();
for(int i=0;i<8;i++){
if(a[now.first+dx[i]][now.second+dy[i]]=='W'){
a[now.first+dx[i]][now.second+dy[i]]='.';
que.push(make_pair(now.first+dx[i],now.second+dy[i]));
}
}
}
ans++;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'){
bfs(i,j);
}
}
}
cout<<ans<<endl;
return 0;
}