[蓝桥杯](布尔类型dfs)全球变暖

题目链接

题意

给定$n\times n$的地图 $.$是水 #是岛屿
一个陆地点在四联通意义上跟水相邻的话 就会被淹没
求图中有多少个岛屿会被完全淹没

思路

数据范围　$$n<=1000$$

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1010,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int n;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
char g[N][N];
bool vis[N][N];
bool check(int x,int y){//(x,y)周围有海水的话 return 1
    for(int i=0;i<4;i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]) continue;
        if(g[tx][ty]=='.') return 1;
    }
    return 0;
}
bool dfs(int x,int y){//这块岛屿被全部淹没 就return 1　
    bool flag=1;
    //if(check(x,y)==0) flag=0;//这句放在这里也可以

    for(int i=0;i<4;i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]) continue;
        if(g[tx][ty]=='.') continue;
        
        if(check(tx,ty)==0) flag=0;//周围没海水
        vis[tx][ty]=1;
        bool sub=dfs(tx,ty);//先把dfs的返回值存下来 好习惯 
        if(sub==0) flag=0;
        //if(dfs(tx,ty)==0) flag=0;
    }
    return flag;//周围有海水 返回1 cnt++
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>g[i][j];
    }

    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j]=='#'&&!vis[i][j]){
                vis[i][j]=1;
                if(dfs(i,j)) cnt++;
            }
        }
    }
    cout<<cnt<<endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    
    int T=1;
    // cin>>T;
    while(T--) solve();
}