AcWing 1233. 全球变暖
原题链接
简单
作者:
新嘎坡
,
2022-02-26 09:05:29
,
所有人可见
,
阅读 156
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
char tr[N][N];
bool st[N][N];
int n;
int cnt;
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void bfs(PII start,int & total,int & bound)
{
queue<PII> q;
q.push(start);
st[start.x][start.y]=true;
total++;//将头节点算进去
while(q.size())
{
PII t=q.front();
q.pop();
bool is_bound=false;//用来判断周围是否为海洋
for(int i=0;i<4;i++)
{
int x=t.x+d[i][0],y=t.y+d[i][1];
if(x<0||x>=n||y<0||y>=n) continue;
if(st[x][y]) continue;
if(tr[x][y]=='.')
{
is_bound=true;
continue;//只要相邻的四个方向,有一个方向为海洋,即可记为临界
}
total++;
st[x][y]=true;
q.push({x,y});
}
if(is_bound) bound++;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
scanf("%s",tr[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
PII start;
if(tr[i][j]=='#'&&!st[i][j])
{
int total=0,bound=0;//每次判断都需要赋值为零
start={i,j};
bfs(start,total,bound);
if(total==bound) cnt++;
}
}
cout<<cnt<<endl;
return 0;
}