AcWing 1097. 池塘计数
原题链接
简单
作者:
虚实相依
,
2024-04-22 14:54:57
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010;
typedef pair<int,int> pii;
#define x first
#define y second
char a[N][N];
bool used[N][N];
int ans;
int n,m;
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={-1,-1,0,1,1,1,0,-1};
void bfs(int x,int y)
{
queue<pii> q;
q.push({x,y});
while(q.size())
{
auto tp=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int nex=tp.x+dx[i];
int ney=tp.y+dy[i];
if(nex>=1 && nex<=n && ney>=1 && ney<=m && a[nex][ney]=='W' && !used[nex][ney])
{
q.push({nex,ney});
used[nex][ney]=true;
}
}
a[tp.x][tp.y]='.';
}
}
int main()
{
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),ans++;
}
cout<<ans<<endl;
return 0;
}