算法1
思路
dfs找连通块,在找连通块的过程中判断是否有一种这样的块,他的四周都是陆地,如果有这样的块,意味着这片岛屿不会消失。如果main中判断trueblock = 0, 则这片岛屿会消失,cnt++。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n;
char g[N][N];
int t[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int trueblock;
void dfs(int x, int y)
{
t[x][y] = 1;
if (g[x][y] == '#' && g[x+1][y] == '#' && g[x-1][y] == '#' && g[x][y+1] == '#' && g[x][y-1] == '#')
trueblock++;
for (int i=0; i<4; i++)
{
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == '#' && !t[a][b])
{
dfs(a, b);
}
}
}
int main ()
{
cin >> n;
for (int i=0; i<n; i++)
cin >> g[i];
int cnt = 0;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (g[i][j] == '#' && t[i][j] == 0)
{
dfs(i, j);
if (trueblock == 0)
cnt++;
}
trueblock = 0;
}
}
cout << cnt;
return 0;
}