AcWing 1233. 全球变暖
原题链接
简单
作者:
王小强
,
2021-01-17 19:40:32
,
所有人可见
,
阅读 304
FloodFill 算法 时间复杂度O(N^2)
#include <bits/stdc++.h>
using namespace std;
static constexpr int dirs[] { 0, -1, 0, 1, 0 };
int dfs(vector<vector<char>>& grid, int x, int y, int& sinks) {
if (grid[y][x] == '.' || grid[y][x] == '*') return 0;
grid[y][x] = '*'; // mark as visited
for (int i = 0; i < 4; ++i) {
const int nx = x + dirs[i], ny = y + dirs[i + 1];
if (grid[ny][nx] == '.') {
++sinks;
break;
}
}
int total = 1;
for (int i = 0; i < 4; ++i)
total += dfs(grid, x + dirs[i], y + dirs[i + 1], sinks);
return total;
}
int main() {
int n;
cin >> n;
vector<vector<char>> grid(n, vector<char>(n));
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x)
cin >> grid[y][x];
int ans = 0;
for (int y = 0; y < n; ++y)
for (int x = 0; x < n; ++x)
if (grid[y][x] == '#') {
int sinks = 0; // total岛屿陆地总数, sinks被海水淹没陆地数。
int total = dfs(grid, x, y, sinks);
ans += total == sinks;
}
cout << ans;
return 0;
}