AcWing 1233. 全球变暖
原题链接
简单
作者:
acwing_陌路
,
2021-03-01 21:47:36
,
所有人可见
,
阅读 316
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 1010;
int n;
char g[N][N];
int st[N][N];
typedef pair<int,int> PII;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
void bfs(int sx,int sy,int &total,int &bound)
{
queue<PII> q;
q.push({sx,sy});
st[sx][sy] = true;
while(q.size())
{
PII t = q.front();
q.pop();
total++;
bool is_bound = false;
for(int i = 0;i < 4;i++)
{
int a = t.x + dx[i],b = t.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;
}
q.push({a,b});
st[a][b] = true;
}
if(is_bound) bound++;
}
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i++) scanf("%s",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;
bfs(i,j,total,bound);
if(total == bound)
{
cnt++;
}
}
}
}
cout << cnt << endl;
return 0;
}