当前位置: 首页 > article >正文

[蓝桥杯](布尔类型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();
}

http://www.kler.cn/a/589574.html

相关文章:

  • Ollama + CherryStudio:构建本地私有知识库
  • CC45.【C++ Cont】STL中的哈希表及练习
  • 定时器‘PWM和串口通信(20250317)
  • cesium 实现万级管网数据渲染,及pickImageryLayerFeatures原生方法改写
  • 网络性能指标
  • 五金打磨车间降温设备都哪些?
  • 在 TypeScript 中,两个看似相同的字符串用 `==` 比较返回 `false`
  • 【Agent】OpenManus-Prompt组件详细分析
  • C3P0数据库连接池技术详解及实战
  • 【网站检测工具Web-Check】Web-Check本地部署与远程访问解决方案全面掌控网站状态
  • CentOS 7 更换 YUM 源为国内
  • Android视频渲染SurfaceView强制全屏与原始比例切换
  • 【Go】go语言指针
  • 计算机网络:(二)计算机网络在我国发展与网络类别与性能 (附带图谱更好对比理解)
  • python | 输入日期,判断这一天是这一年的第几天
  • 基于CPLD电力/轨道交通3U机箱开关量输出板(DO)
  • KV 缓存简介
  • 最长最短单词(信息学奥赛一本通-1143)
  • 京东Taro小程序原生端接入操作
  • 第四十八篇——数学和其它学科:为什么数学是更底层的工具?