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)是一个逻辑概念,用于组织数据库中的对象。模式中的对象通常包括表、索引、数据类型、序列、视图、存储过程、主键、外键等等。 模式可以为数据库对象提供逻辑隔离功能,不用应用程序可以…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...