AcWing 1097. 池塘计数
原题链接
简单
作者:
我是java同学
,
2023-02-07 05:30:29
,
所有人可见
,
阅读 151
bfs
bfs
特点
- 洪水灌溉算法
- 连通类型
- 四连通——偏移量
- 八连通——两重循环,特判中间格子
- 思路:从前往后扫描,当扫描到一片水,且水还没有被标记过,那么从这个点开始做,把周围是水的区域标记】
- 下标的存储:pair
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
char g[N][N];
bool st[N][N];
PII q[N * N];
void bfs(int sx, int sy)
{
int hh = 0, tt = -1;
q[ ++ tt] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = t.x - 1; i <= t.x + 1; i ++ )
for (int j = t.y - 1; j <= t.y + 1; j ++ )
{
if (i == t.x && j == t.y) continue;
if (i < 0 || i >= n || j < 0 || j >= m) continue;
if (g[i][j] == '.' || st[i][j]) continue;
q[ ++ tt] = {i, j};
st[i][j] = true;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'W' && !st[i][j])
{
bfs(i, j);
cnt ++ ;
}
cout << cnt << endl;
return 0;
}