【蓝桥杯每日一题】4.2 全球变暖

news/2024/6/16 10:08:53/文章来源:https://blog.csdn.net/qq_63446418/article/details/137292320

原题链接:1233. 全球变暖 - AcWing题库

由题意可知:

  • 需要找到淹没的岛屿的数量
  • 淹没的岛屿所具备的条件:咩有“高地”,也就是说岛屿(连通块)中的所有元素的 4 4 4-邻域中均含有’ . ’

思路1:

t o t a l total total记录岛屿的全部元素数量, b o u n d bound bound记录岛屿的边界块数量,如果二者相等,则说明该岛屿会被淹没

dfs代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;char a[N][N];
bool vis[N][N];
int n;
int res;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; //移动方向
bool flag=false; //插眼,看是否满足周围四个全是#void dfs(int x,int y,int& total,int& bound) //total为联通块个数,bound为边界块个数
{vis[x][y]=1; //记录已经遍历过total++;bool is_bound=false;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//边界值的判断if(nx<0||ny<0||nx>=n||ny>n) continue;if(vis[nx][ny]) continue;if(a[nx][ny]=='.') {is_bound=true;continue;}dfs(nx,ny,total,bound);}if(is_bound) bound++;return;
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++) cin>>a[i]; //cin处理字符串更为方便//遍历for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]=='#'&&!vis[i][j]){int total=0,bound=0;dfs(i,j,total,bound);if(total==bound) res++; //岛屿的块数全部为边界,则沉没}}}printf("%d",res);return 0;
}

思路2:

  • 直接搜索没有“高地”的连通块,用 f l a g flag flag值标记一下是否带有“高地”

bfs代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;int n;
char a[N][N]; 
int vis[N][N]={0};  
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; //移动方向int main()
{scanf("%d",&n);for(int i = 1; i <= n; i++) cin>>a[i]; //cin处理字符串更加方便int res = 0;//进行BFSfor(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(a[i][j]=='#' && vis[i][j]==0) {queue<pair<int, int>> q;q.push({i, j});vis[i][j] = 1;bool flag = true;while(!q.empty()) {int x = q.front().first;int y = q.front().second;q.pop();if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')flag = false;for(int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0 && a[nx][ny] == '#') {q.push({nx, ny});vis[nx][ny] = 1;}}}if(flag)res++; // 统计被淹没的岛的数量}}}printf("%d",res);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034771.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【六 (2)机器学习-机器学习建模步骤/kaggle房价回归实战】

一、确定问题和目标&#xff1a; 1、业务需求分析&#xff1a; 与业务团队或相关利益方进行深入沟通&#xff0c;了解他们的需求和期望。 分析业务流程&#xff0c;找出可能的瓶颈、机会或挑战。 思考机器学习如何帮助解决这些问题或实现业务目标。 2、问题定义&#xff1a;…

Java | Leetcode Java题解之第8题字符串转换整数atoi

题目&#xff1a; 题解&#xff1a; class Solution {public int myAtoi(String str) {Automaton automaton new Automaton();int length str.length();for (int i 0; i < length; i) {automaton.get(str.charAt(i));}return (int) (automaton.sign * automaton.ans);} …

基础布局之LinearLayout线性布局

目录 一、基础属性二、重点属性2.1 weight(权重)属性&#xff1a;2.2 gravity 一、基础属性 LinearLayout默认方向是水平排放 属性作用android:id控件的ID&#xff0c;可以通过这个ID号来找到对应的控件android:layout_width控件的宽度android:layout_height控件的高度androi…

[C语言实现]数据结构二叉树之《我种下的树会为我遮阳挡雨》

&#x1f970;作者: FlashRider &#x1f30f;专栏: 初阶数据结构 &#x1f356;知识概要&#xff1a;详解二叉树的概念、二叉树的遍历、以及代码实现。 目录 树的基本概念 树的存储结构与二叉树的实现 树的存储 什么是二叉树 二叉链存储二叉树 二叉树的代码实现 树的基本…

gpt 3d三角形 重心坐标填充 沿x轴炫赵师傅

go import pygame from pygame.locals import * import sys import math# 初始化Pygame pygame.init()# 设置窗口大小 width, height 800, 600 screen pygame.display.set_mode((width, height)) pygame.display.set_caption(3D Triangle Fill with Barycentric Coordinates)…

海豚调度任务类型Apache SeaTunnel部署指南

Apache DolphinScheduler已支持Apache SeaTunnel任务类型&#xff0c;本文介绍了SeaTunnel任务类型如何创建&#xff0c;任务参数&#xff0c;以及任务样例。 一、Apache SeaTunnel SeaTunnel 任务类型&#xff0c;用于创建并执行 SeaTunnel 类型任务。worker 执行该任务的时…

Kaggle:收入分类

先看一下数据的统计信息 import pandas as pd # 加载数据&#xff08;保留原路径&#xff0c;但在实际应用中建议使用相对路径或环境变量&#xff09; data pd.read_csv(r"C:\Users\11794\Desktop\收入分类\training.csv", encodingutf-8, encoding_errorsrepl…

基于单片机智能输液器监控系统的设计

**单片机设计介绍&#xff0c;基于单片机智能输液器监控系统的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机智能输液器监控系统的设计旨在实现对输液过程的实时监测和控制&#xff0c;以提高输液的安全性和疗效…

C++:函数重载,引用

文章目录 1. 函数重载1.1 函数重载概念1.2 C支持函数重载的原理--名字修饰1.3 缺省参数与重载 2. 引用2.1引用概念2.2 引用特性2.3 常引用2.4 使用场景2.5 引用和指针的区别 1. 函数重载 1.1 函数重载概念 C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名…

氮气柜常用的制作材质有哪些?

氮气柜主要用于存储对湿度敏感或需要在低氧环境中保存的精密部件、电子元器件、化学品、文物等&#xff0c;需要确保柜体的密闭性和内部环境的稳定&#xff0c;以防止氧化、受潮或变质。 常见的材质有冷轧钢板&#xff0c;冷轧钢板通过冷轧工艺使钢材组织更紧密&#xff0c;从而…

OpenHarmony实战:Vmware虚拟机和Ubuntu安装

避坑指南 1. 虚拟机命名、用户名称、路径不能有汉字 名称或者路径有汉字&#xff0c;导致输入失败或者安装失败 2. 虚拟机处理器内核总数&#xff08;处理器数量 X 每个处理器的内核数量&#xff09;不得超过电脑逻辑处理器总个数 太少时&#xff0c;下载代码和编译非常缓慢…

go连接数据库(原生)

根据官网文档 Go Wiki: SQL Database Drivers - The Go Programming Language 可以看到go可以连接的关系型数据库 ​ 常用的关系型数据库基本上都支持&#xff0c;下面以mysql为例 下载mysql驱动 打开上面的mysql链接 GitHub - go-sql-driver/mysql: Go MySQL Driver i…

图神经网络实战(7)——图卷积网络(Graph Convolutional Network, GCN)详解与实现

图神经网络实战&#xff08;7&#xff09;——图卷积网络详解与实现 0. 前言1. 图卷积层2. 比较 GCN 和 GNN2.1 数据集分析2.2 实现 GCN 架构 小结系列链接 0. 前言 图卷积网络 (Graph Convolutional Network, GCN) 架构由 Kipf 和 Welling 于 2017 年提出&#xff0c;其理念是…

JavaScript实现全选、反选功能(Vue全选、反选,js原生全选、反选)

简介&#xff1a; 在JavaScript中&#xff0c;实现全选和反选通常是通过操作DOM元素和事件监听来实现&#xff1b; 全选功能&#xff1a;当用户点击一个“全选”复选框时&#xff0c;页面中所有具有相同类名的复选框都将被选中&#xff1b; 反选功能&#xff1a;用户点击一个…

正则表达式(1)

文章目录 专栏导读1、match2、匹配目标3、通用匹配4、常用匹配规则表格 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN 数据分析领域优质创作者&#xff0c;专注于分享python数据分析领域知识。 ✍ 本文录入于《python网络爬虫实战教学》&#xff0c;本专栏针对大学生…

GPT4不限制使用次数了!GPT5即将推出了!

今天登录到ChatGPT Plus账户&#xff0c;出现了如下提示&#xff1a; 已经没有了数量和时间限制的提示。 更改前&#xff1a;每 3 小时限制 40 次&#xff08;团队计划为 100 次&#xff09;&#xff1b;更改后&#xff1a;可能会应用使用限制。 GPT-4放开限制 身边订阅了Ch…

kanzi运行时节点状态展示

背景&#xff1a;有时候kanzi运行后节点不显示&#xff0c;可能是visible/opacity等属性设置不正确&#xff0c;排查困难。做一个实时节点树&#xff0c;方便查看节点信息。 1. 引入imgui 在vs工程里导入glad,glfw,imgui代码 vs属性-链接库&#xff0c;增加glfw3.lib 2. 实现…

js手持小风扇

文章目录 1. 演示效果2. 分析思路3. 代码实现 1. 演示效果 2. 分析思路 先编写动画&#xff0c;让风扇先转起来。使用 js 控制动画的持续时间。监听按钮的点击事件&#xff0c;在事件中修改元素的animation-duration属性。 3. 代码实现 <!DOCTYPE html> <html lang…

Redis 主从复制集群搭建及其原理

目录 前言 配置文件 启动服务 配置主从关系 两种配置方式 slaveof 配置文件 补充 缺点 认证 复制原理 全量同步 增量同步 前言 单机的 redis 的性能虽然已经很强大了&#xff0c;但是随着业务的扩展&#xff0c;总有一天会遇到性能瓶颈&#xff0c;针对高并发带来…

java数组与集合框架(一) -- 数据结构,数组

数据结构 概述 为什么要讲数据结构&#xff1f; 任何一个有志于从事IT领域的人员来说&#xff0c;数据结构&#xff08;Data Structure&#xff09;是一门和计算机硬件与软件都密切相关的学科&#xff0c;它的研究重点是在计算机的程序设计领域中探讨如何在计算机中组织和存储…