🌟DFS_Bool型
🍎解题思路
1.dfs每一个联通块,同时验证是否联通块中是否有上下左右都是’#’的节点,有的话,那么逐层返回ture
2.输出会被淹没的岛屿的数量,dfs == 0代表会被淹没
🍭技巧
1.根据题目需求,每一层dfs的逻辑确定好,注意flag |= dfs,不然flag 可能会被覆盖掉,或者特判如果满足直接返回也ok
🍇时间复杂度
O(N^2)
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;
const int N = 1010;
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char g[N][N];
bool vis[N][N];
int n;
bool dfs(int x, int y)
{
vis[x][y] = 1;
int tx, ty;
bool flag = 0; //会被淹没
int cnt = 0;
rep(i, 0, 4)
{
tx = x + d[i][0], ty = y + d[i][1];
if(tx < 1 || tx > n || ty < 1 || ty > n || g[tx][ty] == '.')
continue;
//与正常dfs不同的是,访问过的点要判断是不是‘#’,还要统计'#'的嗷
cnt++;
if(!vis[tx][ty])
flag |= dfs(tx, ty); //不会被淹没
}
return cnt == 4 || flag; //当前节点不会被淹没 或者 dfs过的节点不会被淹没
}
int main()
{
cin >> n;
rep(i, 1, n + 1)
rep(j, 1, n + 1)
cin >> g[i][j];
int ans = 0; //统计多少岛屿会被淹没
rep(i, 1, n + 1)
rep(j, 1, n + 1)
{
if(vis[i][j])
continue;
if(g[i][j] == '#' && !dfs(i, j)) //统计会被完全淹没的数量
ans++;
}
cout << ans << endl;
return 0;
}