蓝桥杯2018省赛全球变暖dfs
全球变暖
- ==问题描述==
- ==格式输入==
- ==格式输出==
- ==样例输入==
- ==样例输出==
- ==评测用例规模与约定==
- ==解析==
- ==参考程序==
问题描述

格式输入

格式输出
输出一个整数
样例输入

样例输出
1
评测用例规模与约定
- 最大运行时间:1s
- 最大运行内存: 256M
解析
采用dfs的方式进行搜索,首先输入地图之后进行搜索判断所有岛屿的数量,所有不会被淹没的岛屿的数量(因为只要有一块不和水相接就可以判断为是不会被淹没的所以才取它),然后相减即可得到被淹没的岛屿的数量。
参考程序
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e4+4;
char area[N][N];
bool flag;
int cnt;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//往四个方向走
int ans=0;//没有被淹没岛屿的数量
int res=0;//岛屿的总数量
//用DFS判断搜到的这个岛屿会不会被淹没
void dfs(int x,int y)
{if(flag==false){ //一个岛屿只要有一个点满足就不会变淹没了cnt = 0;for(int i=0; i<4; i++){int tx=d[i][0]+x;int ty=d[i][1]+y;if(area[tx][ty]!='.')cnt++;}if(cnt==4){//有一个点满足不会被淹没的条件ans++;flag=true;//这个岛屿不需要再遍历了}}area[x][y]='*';//将遍历过的点变为 *,下一次就不会遍历了,所以不用标记数组//注意这里不可以是‘.’因为上面if(area[tx][ty]!='.')cnt++for(int i=0;i<4;i++){int xx = x + d[i][0];int yy = y + d[i][1];if(area[xx][yy]=='#'&&x<N&&x>=0&&y<N&&y>=0)dfs(xx,yy);}
}int main()
{ cin>>n; for(int i=0; i<n; i++)for(int j=0; j<n; j++)cin>>area[i][j];for(int i=0; i<n; i++){ for(int j=0; j<n; j++){if(area[i][j]=='#'){res++;flag=false;dfs(i,j);}}} cout<<res-ans; return 0;
}
以个人刷题整理为目的,如若侵权,请联系删除~
相关文章:
蓝桥杯2018省赛全球变暖dfs
全球变暖 问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序 问题描述 格式输入 格式输出 输出一个整数 样例输入 样例输出 1 评测用例规模与约定 最大运行时间:1s最大运行内存: 256M 解析 采用dfs的方式进行搜索,首先输入地…...
Bean的作用域 - spring
前言 本篇介绍Bean的6种作用域,与通过注释修改作用域的方式,如有错误,请在评论区指正,让我们一起交流,共同进步! 文章目录 前言1. Bean的作用域1.1 singleton - 单例模式 - 默认作用域1.2 prototype - 原型…...
[ncnn]ncnnoptimize使用
usage: ncnnoptimize [inparam] [inbin] [outparam] [outbin] [flag] [cutstart] [cutend] 使用案例: ./ncnnoptimize yolov5s_6.2.param yolov5s_6.2.bin yolov5s_6.2_opt.param yolov5s_6.2_opt.bin 65536ncnnoptimize [原模型param文件] [原模型bin文件] [新模…...
Elasticsearch笔记
迈向光明之路,必定荆棘丛生。 文章目录 一、Elasticsearch概述二、初识ES倒排索引1. 正向索引2. 倒排索引 三、ES环境搭建1. 安装单机版ES2. 安装Kibana3. 安装ik分词器3.1 在线安装ik插件3.2.离线安装ik插件(推荐方式)3.3 自定义词典 四、ES…...
《怎样顺利通过答辩:论文答辩的策略与技巧》
最近在阅读《怎样顺利通过答辩这本书》,记录一下阅读获取的关键信息和心得。 目录 第一章 答辩是什么 在答辩前你需要做到以下几件事情,核查清单如下: 答辩根据考生及其研究的质量,服务于不同的目的: 通常意义上的…...
uniapp 微信小程序:页面+组件的生命周期顺序
uniapp 微信小程序:页面组件的生命周期顺序 首页页面父组件子组件完整顺序参考资料 这个uniapp的微信小程序项目使用的是 VUE2 首页 首页只提供了一个跳转按钮。 <template><view><navigator url"/pages/myPage/myPage?namejerry" hov…...
Linux CentOS 8 编译安装Apache Subversion
前言 距离上一篇发表已经过去了5年零2个多月,这次重新开始写技术博客,理由和原来一样,也就是想把自己学习和工作中遇到的问题和知识记录下来,今天记录一下Linux CentOS 8通过编译安装svn的过程。 下载SVN 下载地址:…...
谈一谈缓存穿透,击穿,雪崩
缓存穿透 缓存穿透是指在使用缓存系统时,频繁查询一个不存在于缓存中的数据,导致这个查询每次都要通过缓存层去查询数据源,无法从缓存中获得结果。这种情况下,大量的请求会直接穿透缓存层,直接访问数据源,…...
如何对反编译的安卓应用进行调试并修改
安卓修改大师可以在没有源代码的情况下,直接反编译已经打包的APK安装包,通过修改SMALI代码实现添加和去除部分功能,并在应用的任何地方添加任意代码,增加任意任何您想实现的功能。通过这种方式,把该应用变为您自己的应…...
C#实现数据库数据变化监测(sqlservermysql)
监测数据库表数据变化,可实现数据库同步(一主一从(双机备份),一主多从(总部数据库,工厂1,工厂2,工厂数据合并到总部数据)) sqlserver 启用数据库…...
MFC第二十三天 HBrush对闭合图形的填充、CPen、CFont类常用功能与LOGFONT和LOGPEN结构体
文章目录 HBrush对闭合图形的填充HBITMAP位图资源的加载和平铺填充CFont类常用功能与LOGFONT结构体CPen类简介 HBrush对闭合图形的填充 HBRUSH创建: a)实色填充: HBRUSH CreateSolidBrush( COLORREF color);b)栅格线填充: HBRUSH CreateHa…...
深入学习 Redis - 渐进式遍历 scan 命令、数据库管理命令
目录 前言 一、scan 命令 二、数据库管理命令 select dbsize flushdb / flushall 前言 之前我们所了解到的 keys * 是一次性把整个 redis 中所有的 key 都获取到,但是整个操作比较危险,可能会一下子的都太多的 key,阻塞 redis 服务器. …...
python+opencv实现显示摄像头,截取相关图片,录取相关视频
实时显示摄像头图像 按下空格键,截取图片 按下tab键,开始录制摄像内容,再次按下,结束录制 按下Esc键,关闭窗口 import cv2 import numpy#第几章图片 img_count0InitVideoFalse #第几个视频 video_count0 video_flagFa…...
第十章:重新审视扩张卷积:一种用于弱监督和半监督语义分割的简单方法
0.摘要 尽管取得了显著的进展,弱监督分割方法仍然不如完全监督方法。我们观察到性能差距主要来自于它们在从图像级别监督中学习生成高质量的密集目标定位图的能力有限。为了缓解这样的差距,我们重新审视了扩张卷积[1]并揭示了它如何以一种新颖的方式被用…...
指令收集:DOCKER+K8S
docker 1.镜像指令:docker images 1、docker images : 列出本地主机上的镜像OPTION字段说明: -a 列出所有本地镜像, -q 只显示镜像ID2、docker search 某个镜像名字 : 查找某个镜像加上 --limit 5 redisÿ…...
Minecraft 1.20.x Forge模组开发 05.矿石生成
我们本次尝试在主世界生成模组中自定义的矿石 效果演示 效果演示 效果演示 1.由于1.20的版本出现了深板岩层的矿石,我们要在BlockInit类中声明一个矿石的两种岩层形态: BlockInit.java package com.joy187.re8joymod.init;import java.util.function.Function;import java…...
运维面试大全
文章目录 第一阶段你是用过哪些Linux命令Linux 系统安全优化与内核优化经常使用shell脚本做什么软连接与硬链接的区别怎么查看文件IOS七层模型三次握手与四次挥手lvm 逻辑卷创建过程磁盘配额raid 磁盘阵列文本三剑客防火墙iptables与firewardLinux系统资源查询命令日志的八大等…...
【线程安全的讨论(一)】CPU多核缓存架构和JMM
CPU多核缓存架构 一、CPU多核缓存架构可见性问题乱序执行(指令重排) 二、JMM——Java内存模型 一、CPU多核缓存架构 计算机的基本组成图 CPU 缓存为了提高程序运行的性能,现代 CPU 在很多方面会对程序进行优化。CPU 的处理速度很快…...
以太网交换机的生成树协议STP
概述 网络环路带来的问题 广播风暴 广播帧在各个交换机之间反复转发,分别按顺时针和逆时针方向不停的同时兜圈。广播风暴会大量消耗网络资源,使得网络无法正常转发其他数据帧。 主机收到反复的广播帧,会大量消耗主机的资源。交换机的帧交换…...
手机照片转换成pdf怎么做?了解这几种方法就可以了
手机照片转换成pdf怎么做?转换照片为PDF的需求在日常生活中很常见。无论是收集有关旅行、家庭或工作的照片,将它们组织成一个PDF文件可以更方便地分享给朋友或同事。那么下面就给大家分享几个手机照片转换成pdf的方法。 虽然有多种软件和工具可以将照片转…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
智警杯备赛--excel模块
数据透视与图表制作 创建步骤 创建 1.在Excel的插入或者数据标签页下找到数据透视表的按钮 2.将数据放进“请选择单元格区域“中,点击确定 这是最终结果,但是由于环境启不了,这里用的是自己的excel,真实的环境中的excel根据实训…...
[特殊字符] Spring Boot底层原理深度解析与高级面试题精析
一、Spring Boot底层原理详解 Spring Boot的核心设计哲学是约定优于配置和自动装配,通过简化传统Spring应用的初始化和配置流程,显著提升开发效率。其底层原理可拆解为以下核心机制: 自动装配(Auto-Configuration) 核…...
构建Docker镜像的Dockerfile文件详解
文章目录 前言Dockerfile 案例docker build1. 基本构建2. 指定 Dockerfile 路径3. 设置构建时变量4. 不使用缓存5. 删除中间容器6. 拉取最新基础镜像7. 静默输出完整示例 docker runDockerFile 入门syntax指定构造器FROM基础镜像RUN命令注释COPY复制ENV设置环境变量EXPOSE暴露端…...
