[蓝桥杯](布尔类型dfs)全球变暖
题目链接
题意
给定
n
×
n
n\times n
n×n的地图
.
.
.是水 #是岛屿
一个陆地点在四联通意义上跟水相邻的话 就会被淹没
求图中有多少个岛屿会被完全淹没
思路
数据范围 n < = 1000 n<=1000 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();
}