flood fill算法
解题思路:
- 统计有几个合法陆地进行搜索
- 搜索每一片土地,并判断这片土地的单元总数是否等于会被淹没的单元总数
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 1010
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
char g[N][N];
bool st[N][N];
PII q[N*N];
int n;
int dx[] = {-1,0,1,0} , dy[] = {0,-1,0,1};
void bfs(int x,int y,int &total,int &bound)
{
int hh = 0 , tt = 0;
q[0] = {x,y};
st[x][y] = 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; //检查x,y四周是否有海
continue; //既然这个单元是海,那就直接跳过
}
q[++ tt] = {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 ++;
}
printf("%d\n",cnt);
return 0;
}