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

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 定义标识符&#x1…...

2023最新量化优选股票参考(2.9)

还是周一发的那些股票(可以看我周一的文章),安心持仓就好,跑赢指数是大概率的事情,也大概率获得正收益。 其实我知道大家都没法全天一直看盘操作,毕竟要工作,我也是一样,没法一直看盘…...

深眸科技以科技赋能智慧物流搭建,实现周转箱拆垛作业智能化

数字化时代下市场竞争的核心要素转化为科技的竞争,智能化技术的投入是企业占据市场竞争绝对优势的重要支撑。深眸科技凭借轻辙视觉引擎实现周转箱拆垛作业的智能化突破。人力成本增加,企业积极转变特别是在后疫情时代,人力成本迅猛增加&#…...

R数据分析:孟德尔随机化中介的原理和实操二

delta方法 上面的流程跑通之后,对于中介分析,我们需要报告间接效应的估计值和置信区间,还有中介比例的估计值和置信区间,类似下面的这样: 但是其实我们是光跑孟德尔是得不到上面的需要的值的(比如间接效应…...

【SQL开发实战技巧】系列(十二):三问(如何对字符串字母去重后按字母顺序排列字符串?如何识别哪些字符串中包含数字?如何将分隔数据转换为多值IN列表?)

系列文章目录 【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧…...

数据库模式(schema)是什么?

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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

EtherNet/IP转DeviceNet协议网关详解

一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

LangFlow技术架构分析

🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...