Python:每日一题之全球变暖(DFS连通性判断)
题目描述
你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 N (1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出一个整数表示答案。
输入输出样例
示例
输入
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出
1
思路:
连通性判断:图论的一个简单问题,给定一张图,图由点和连接点的边组成,要求找到图中互相连通的部分。
连通性问题,计算步骤:
>遍历一个连通块(找到这个连通块中所有的'#',标记已经搜过,不用再搜);
>再遍历下一个连通块….;
>遍历完所有连通块,统计有多少个连通块。
什么岛屿不会被完全淹没?
>若岛中有个陆地(称为高地),它周围都是陆地,那么这个岛不会被完全淹没。
>用DFS搜出有多少个岛(连通块),检查这个岛有没有高地,统计那些没有高地的岛(连通块)的数量,就是答案。计算复杂度:每个像素点只用搜一次且必须至少搜一次,共N^2个点,DFS的复杂度是O(N^2),不可能更好了。
>从图上任意一个点u开始遍历,标记u已经搜过。
>递归u的所有符合连通条件的邻居点。
>递归结束,找到了与u连通的所有点,这是一个连通块。
>不与u连通的、其他没有访问到的点,继续用上述步骤处理,找到所有的连通块。
参考代码:
import sys
sys.setrecursionlimit(60000)
def dfs(x,y):d=[(0,1),(0,-1),(1,0),(-1,0)] #左 右 上 下 四个方向global flagglobal visglobal mpvis[x][y]=1if mp[x][y+1]=='#' and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1for i in range(4):nx=x+d[i][0]ny=y+d[i][1]if vis[nx][ny]==0 and mp[nx][ny]=="#":dfs(nx,ny)
n=int(input())
mp=[]
for i in range(n):mp.append(list(input()))
vis=[]
for i in range(n):vis.append([0]*n)
ans=0
for i in range(n):for j in range(n):if vis[i][j]==0 and mp[i][j]=='#':flag=0dfs(i,j)if flag==0:ans+=1
print(ans)
相关文章:
Python:每日一题之全球变暖(DFS连通性判断)
题目描述 你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示: ....... .##.... .##.... ....##. ..####. ...###. ....... 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿…...

企业级安全软件装机量可能大增
声明 本文是学习大中型政企机构网络安全建设发展趋势研究报告. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 研究背景 大中型政企机构是网络安全保护的重中之重,也是国内网络安全建设投入最大,应用新技术、新产品最多的机构…...

为什么要用频谱分析仪测量频谱?
频谱分析仪是研究电信号频谱结构的仪器,用于信号失真度、调制度、谱纯度、频率稳定度和交调失真等信号参数的测量,可用以测量放大器和滤波器等电路系统的某些参数,是一种多用途的电子测量仪器。从事通信工程的技术人员,在很多时候…...

Python环境搭建、Idea整合
1、学python先要下载什么? 2、python官网 3、idea配置Python 4、idea新建python 学python先要下载什么? python是一种语言,首先你需要下载python,有了python环境,你才可以在你的电脑上使用python。现在大多使用的是pyt…...

HTTP请求返回304状态码以及研究nginx中的304
文章目录1. 引出问题2. 分析问题3. 解决问题4. 研究nginx中的3044.1 启动服务4.2 ETag说明4.3 响应头Cache-Control1. 引出问题 之前在调试接口时,代码总出现304问题,如下所示: 2. 分析问题 HTTP 304: Not Modified是什么意思? …...

【GD32F427开发板试用】使用Arm-2D显示电池电量
本篇文章来自极术社区与兆易创新组织的GD32F427开发板评测活动,更多开发板试用活动请关注极术社区网站。作者:boc 【虽迟但到】 由于快递的原因,11月份申请的,12月1日才收到GD32F427开发板。虽然姗姗来迟,但也没有减少…...
TS第二天 Typesrcipt编译
文章目录自动编译tsconfig.json配置选项include 比较重要excludeextendsfilescompilerOptions 比较重要自动编译 手动模式:每次ts文件修改完,手动编译一次 tsc 01.ts监视模式:ts文件修改完,自动监视编译 tsc 01.ts -w编译所有文…...

基于C#制作一个飞机大战小游戏
此文主要基于C#制作一个飞机大战游戏,重温经典的同时亦可学习。 实现流程1、创建项目2、界面绘制3、我方飞机4、敌方飞机5、子弹及碰撞检测实现流程 1、创建项目 打开Visual Studio,右侧选择创建新项目。 搜索框输入winform,选择windows窗体…...

git修改历史提交(commit)信息
我们在开发中使用git经常会遇到想要修改之前commit的提交信息,这里记录下怎么使用git修改之前已经提交的信息。一、修改最近一次commit的信息 首先通过git log查看commit信息。 我这里一共有6次commit记录。 最新的commit信息为“Merge branch ‘master’ of https:…...

代码解析工具cpg
cpg 是一个跨语言代码属性图解析工具,它目前支持C/C (C17), Java (Java 13)并且对Go, LLVM, python, TypeScript也有支持,在这个项目的根目录下: cpg-core为cpg解析模块的核心功能,主要包括将代码解析为图,core模块只包括对C/C/Ja…...
Linux虚拟机部署Java环境-Jdk-Mysql
Linux虚拟机部署 author hf 1.安装 电脑安装x-shell工具,然后使用堡垒机基础控件windows版进行安装扫描,最后点击自动检测,保证能扫描到X-shell工具的安装路径 使用堡垒机登录快照夏选择工具点击Xshell进行连接 查看linux版本 root:~# ca…...

每日学术速递2.9
CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV、cs.AI、cs.LG、cs.IR 1.Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution(ICLR 2023) 标题:归纳单比特矩阵完成的图信号采样&am…...

【Linux】进程优先级 | 进程的切换 | 环境变量详解
🤣 爆笑教程 👉 《看表情包学Linux》👈 猛戳订阅 🔥 💭 写在前面:我们先讲解进程的优先级,探讨为什么会存在优先级,以及如何查看系统进程、进程优先级的修改。然后讲解进程的切…...

leaflet 实现左卷帘效果 (代码示例045)
第045个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中实现左卷帘效果,这里主要引用了leaflet-side-by-side这个插件,直接调用的话,CSS方面有些问题,需要自行调整一下。 直接复制下面的 vue+leaflet源代码,操作2分钟即可运行实现效果 文章目录 示例效果配…...

程序的翻译环境和执行环境
程序环境和预处理🦖程序的翻译环境和执行环境🦖详解编译链接🐳 翻译环境🐳 详解编译过程🐳 运行环境🦖预处理详解🐳 预定义符号🐳 #define🦀 #define 定义标识符…...
2023最新量化优选股票参考(2.9)
还是周一发的那些股票(可以看我周一的文章),安心持仓就好,跑赢指数是大概率的事情,也大概率获得正收益。 其实我知道大家都没法全天一直看盘操作,毕竟要工作,我也是一样,没法一直看盘…...

深眸科技以科技赋能智慧物流搭建,实现周转箱拆垛作业智能化
数字化时代下市场竞争的核心要素转化为科技的竞争,智能化技术的投入是企业占据市场竞争绝对优势的重要支撑。深眸科技凭借轻辙视觉引擎实现周转箱拆垛作业的智能化突破。人力成本增加,企业积极转变特别是在后疫情时代,人力成本迅猛增加&#…...
R数据分析:孟德尔随机化中介的原理和实操二
delta方法 上面的流程跑通之后,对于中介分析,我们需要报告间接效应的估计值和置信区间,还有中介比例的估计值和置信区间,类似下面的这样: 但是其实我们是光跑孟德尔是得不到上面的需要的值的(比如间接效应…...
【SQL开发实战技巧】系列(十二):三问(如何对字符串字母去重后按字母顺序排列字符串?如何识别哪些字符串中包含数字?如何将分隔数据转换为多值IN列表?)
系列文章目录 【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧…...

数据库模式(schema)是什么?
在数据库的术语中,模式(schema)是一个逻辑概念,用于组织数据库中的对象。模式中的对象通常包括表、索引、数据类型、序列、视图、存储过程、主键、外键等等。 模式可以为数据库对象提供逻辑隔离功能,不用应用程序可以…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...