题目描述
blablabla
思路:想办法判断哪几个陆地是一坨的
并查集的思想,只要找到一个没被标记过的,并且是个陆地
就疯狂bfs他周围的小陆地,如果下个状态的是个正常的小陆地,把他入队列
样例
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int ,int >PII;
const int N=1010;
char g[N][N];
bool st[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n;
PII q[N*N];
void bfs(int sx,int sy, int &total, int &bound)
{
int hh=0,tt=0;
q[0]={sx,sy};
st[sx][sy]=true;
while(hh<=tt)
{
PII t=q[hh++];
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[++tt]={a,b};
st[a][b]=true;
}
if(is_bound) bound++;
}
}
int main()
{
cin>>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;
}