AcWing 5565. 残垣断壁
原题链接
中等
作者:
小趴菜AC不了
,
2024-04-08 22:14:18
,
所有人可见
,
阅读 6
模板题
foold fill;
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
bool st[N][N];
int n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int a,int b)
{
queue<PII>q;
q.push({a,b});
st[a][b] = true;
while(q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
for (int j = 0; j < 4; j ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m)continue;
if(g[x][y] == '.')continue;
if(g[x][y] == 'B' && !st[x][y] )
{
st[x][y] = true;
q.push({x,y});
}
}
}
}
int main()
{
cin>>n>>m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin>>g[i][j];
int res = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if(!st[i][j] && g[i][j]=='B')
{
bfs(i,j);
res++;
}
cout << res;
return 0;
}