AcWing 1233. 全球变暖
原题链接
简单
作者:
铁门栓
,
2024-04-01 20:31:25
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 1010;
char a[N][N];
bool st[N][N];
int n;
void bfs(int x1,int y1,int& cut,int& bot) {
queue<PII> q;
q.push({x1,y1});
st[x1][y1] = true;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
while(!q.empty()) {
auto t = q.front();
q.pop();
cut ++;
bool is_bot = false;
for (int i = 0;i < 4;i++) {
int c = t.x + dx[i];
int d = t.y + dy[i];
if (c < 0 || c >= n || d < 0 || d >= n) continue;
if (st[c][d]) continue;
if (a[c][d] == '.') {
is_bot = true;
continue;
}
if (a[c][d] == '#') {
q.push({c,d});
st[c][d] = true;
}
}
if (is_bot) bot++;
}
}
int main() {
scanf("%d",&n);
for (int i = 0;i < n;i++) scanf("%s",a[i]);
int res = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (a[i][j] == '#' && !st[i][j]) {
int cut = 0,bot = 0;
bfs(i,j,cut,bot);
if (cut == bot) res++;
}
}
}
cout << res << endl;
return 0;
}