AcWing 1097. 池塘计数
原题链接
简单
作者:
王小强
,
2021-01-25 18:28:41
,
所有人可见
,
阅读 375
FloodFill 算法模版 Time Complexity: $O(N * M)$
#include <iostream>
using namespace std;
const int N = 1010;
int m, n;
char g[N][N];
static constexpr int dirs[][2] {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1},
{0, 1}, {1, 1}, {1, 0}, {1, -1}};
void dfs(int x, int y) {
if (x < 0 || y < 0 || x == n || y == m || g[y][x] == '.')
return;
g[y][x] = '.'; // mark as seen
for (int i = 0; i < 8; ++i)
dfs(x + dirs[i][0], y + dirs[i][1]);
}
int main() {
cin >> m >> n;
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) cin >> g[y][x];
int ans = 0;
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) {
ans += g[y][x] == 'W';
dfs(x, y);
}
cout << ans << endl;
return 0;
}