AcWing 1233. 全球变暖
原题链接
简单
作者:
EXQS
,
2021-04-13 21:35:14
,
所有人可见
,
阅读 252
#include<iostream>
#include<utility>
#include<queue>
#include<cstdio>
using namespace std;
const int N = 1010;
int ans, n;
char map[N][N];
int vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs(int x, int y) {
vis[x][y] = 1;
queue<pair<int, int>> q;
q.push(make_pair(x, y));
int cnt1 = 0, cnt2 = 0;
while (!q.empty()) {
bool flag = false;
int xx = q.front().first, yy = q.front().second;
q.pop();
cnt1++;
for (int k = 0; k < 4; ++k) {
int i = xx + dx[k], j = yy + dy[k];
if (i >= 0 && i < n && j >= 0 && j < n && map[i][j] == '.')flag = true;
if (i >= 0 && i < n && j >= 0 && j < n && map[i][j] == '#' && vis[i][j] == 0) {
q.push(make_pair(i, j));
vis[i][j] = 1;
}
}
if (flag) {
cnt2++;
}
}
if (cnt1 == cnt2)ans++;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; ++j) {
if (vis[i][j] == 0 && map[i][j] == '#') {
bfs(i, j);
}
}
}
cout << ans << endl;
return 0;
}