AcWing 1233. 全球变暖(DFS,C++)
原题链接
简单
作者:
诺亚方舟.
,
2021-03-10 14:22:57
,
所有人可见
,
阅读 3725
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
bool st[N][N];
char g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int& total, int& bound)
{
st[x][y] = true;
total++; //连通块个数++
bool is_bound = false;
for (int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= n) continue;
if (st[a][b]) continue;
if (g[a][b] == '.')
{
is_bound = true;
continue;
}
dfs(a, b, total, bound);
}
if (is_bound) bound++; //当前块是边界!
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> g[i];
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (!st[i][j] && g[i][j] == '#')
{
int total = 0, bound = 0;
dfs(i, j, total, bound);
if (total == bound) cnt++;
}
cout << cnt << endl;
return 0;
}
tql 用块数等于边界数来判断是否全被淹没
这道题跟寻宝图那题几乎一摸一样,直接一遍过
orz
这递归太香了
%%%%%%