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

Python:每日一题之全球变暖(BFS连通性判断)

题目描述

你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示:

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。

例如上图中的海域未来会变成如下样子:

.......

.......

.......

.......

....#..

.......

.......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

思路:

连通性判断:
图论的一个简单问题,给定一张图,图由点和连接点的边组成,要求找到图中互相连通的部分。
BFS判断连通性的步骤:
        ·从图上任意一个点u开始遍历,把它放进队列中。
        ·弹出队首u,标记u已搜过,然后搜索u的邻居点,即与u连通的点,放到队列中。
        ·继续弹出队首,标记搜过,然后搜索与它连通的邻居点,放进队列。
继续以上步骤,直到队列为空,此时一个连通块已经找到。
其他没有访问到的点,属于另外的连通块,按以上步骤再次处理这些点。
最后所有点都搜到,所有连通块也都找到。
连通性判断
什么岛屿不会被完全淹没?
        >若岛中有个陆地(称为高地),它周围都是陆地,那么这个岛不会被完全淹没。
        >用BFS搜出有多少个岛(连通块),检查这个岛有没有高地,统计那些没有高地的岛(连通块)的数量,就是答案。
        >计算复杂度:每个像素点只用搜一次且必须至少搜一次,共N2个点,BFS的复杂度是O(N2),不可能更好了。

参考代码:

from queue import *  #导入模块
def bfs(x,y):global flag    q=Queue()     #创建队列vis[x][y]=1   #标记使用q.put((x,y))  #放入while not q.empty():  #是否为空x,y=q.get((x,y))   #弹出队头if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地,高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.put((xt,yt))vis[xt][yt]=1n=int(input())
mp=[]
l=[(1,0),(-1,0),(0,-1),(0,1)]
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=0bfs(i,j)if flag==0:ans+=1
print(ans)

用list实现队列 :

def bfs(x,y):global flag    vis[x][y]=1   #标记使用q=[(x,y)]  #放入while q:  #是否为空x,y=q.pop(0)   #弹出队头if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地,高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.append((xt,yt))vis[xt][yt]=1

用deque实现队列:

from collections import *  #导入模块
def bfs(x,y):global flag    vis[x][y]=1   #标记使用q=deque()  q.append((x,y))while q:  #是否为空x,y=q.popleft()   if mp[x][y+1]=="#" and mp[x][y-1]=='#' and mp[x+1][y]=='#' and mp[x-1][y]=='#':flag=1   #判断是否为高地,高地不被淹没for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if vis[xt][yt]==0 and mp[xt][yt]=='#':q.append((xt,yt))vis[xt][yt]=1

建议用队列操作时,使用deque

相关文章:

Python:每日一题之全球变暖(BFS连通性判断)

题目描述 你有一张某海域 NxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示: ....... .##.... .##.... ....##. ..####. ...###. ....... 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿…...

VUE -- defineExpose

defineExpose定义demo定义 defineExpose定义:用于组件通信中父级组件调用操作子组建方法和响应式属性参数能力 在使用definExpose前需要了解两个拷贝对象函数 对象copy:shallowReactive 与 数据 copy:shallowRef 这两个都是vue包里面的 简…...

实用调试技巧【下篇】

🔴本文章是在 Visual Studio 2022(VS2022)编译环境下进行操作讲解 文章目录3.2.调试的时候查看程序当前信息3.2.1.查看临时变量的值3.2.2.查看内存信息3.2.3.查看调用堆栈3.2.4.查看汇编信息🥳4.调试实例🥳5.如何写出&…...

【数据结构期末例题】

前言 本文是博主自己在准备学校数据结构考试时的总结,各个知识点都贴有对应的详细讲解文章以供大家参考;当然文中还有许许多多的截图,这些是博主对主要内容的摘取,对于那些基础较好的同学可以直接看截图,减少跳转对应文…...

管理物理和快照备数据库(Physical and Snapshot Standby Databases)

1.打开物理备数据库 物理备数据库可以打开做只读访问,用于从主数据库卸载查询负载。 如果已经购买Oracle Active Data Guard选项的授权,当数据库打开时Redo Apply可以是激活的,因此允许查询返回与从主数据库返回的完全相同的结果…...

双目立体视觉:SAD算法

算法原理SAD(Sum of absolute differences)是一种图像匹配算法。基本思想:差的绝对值之和。此算法常用于图像块匹配,将每个像素对应数值之差的绝对值求和,据此评估两个图像块的相似度。该算法快速、但并不精确,通常用于多级处理的…...

海外问卷调查答题技巧,纯干货分享,新手小白看过来

海外问卷调查为什么别人赚得盆满钵满而我却连通过都不行?是不是经常有人发出这种疑问,东哥作为一个结交过很多做问卷调查行业的跨境人士,也了解到很多做这一行的去答题的时候都是掌握一定技巧的,而不是去乱答。今天东哥就来说说国…...

【NGINX入门指北】Nginx Web 架构实验

Nginx Web 架构实验 文章目录Nginx Web 架构实验一、动态网站结构二、LNMP 动态网站环境部署三、fastcgi & php-fpm:四、php-fpm初始化配置五、Nginx Location、六、Nginx Rewrite七、CA&HTTPS八、Nginx 的平滑升级一、动态网站结构 资源 资源文件识别——…...

rtt-nano移植

nano其他功能移植 添加finsh组件打开宏实现rt_hw_console_getchar函数添加finsh组件到工程总结问题1. 移植到stm32G0过程中出现Undefined symbol rt_hw_interrupt_disable (referred from clock.o)??2. “implict declaration of function ‘ ‘ is invalid in c99??3. 关于…...

cnn+transformer

好的,下面是使用 Transformer 加 CNN 实现语义分割的代码,使用的数据集是 Semantic Segmentation Drone Dataset。 首先,我们需要导入必要的 Python 库和模块。我们将使用 PyTorch 深度学习框架来实现模型: #python import torch import torch.nn as nn import torch.nn.fu…...

Python fileinput模块:逐行读取多个文件

前面章节中,我们学会了使用 open() 和 read()(或者 readline()、readlines() )组合,来读取单个文件中的数据。但在某些场景中,可能需要读取多个文件的数据,这种情况下,再使用这个组合&#xff0…...

Vue3路由传参

vue3路由和vue2差别不是很大,不过在传参形式上略有改变 在Vue3中使用路由必须引入 useRouter 和 useRoute import { useRoute, useRouter } from vue-routerconst Router useRouter() //跳转const Route useRoute() //获取到值 同Vue2一样,query使用p…...

用户管理——认证功能JWT和Session

目录用户认证功能的技术选型JWT和Session的区别基于JWT和Session的认证流程基于JWT的认证流程基于Session的认证流程基于JWT和Session的认证的优缺点基于JWT和Session的认证的安全性基于JWT和Session的认证的性能分析基于JWT的一次性和无法废弃基于JWT和Session的认证的续签选择…...

hashlib — 加密哈希算法

hashlib — 加密哈希算法 1.概述 加密可以保护消息的安全,以便验证它们的准确性并且使它们受保护不被拦截。 Python 的加密方式支持包括利用像 MD5 和 SHA 这样的标准算法对消息内容产生签名的 hashlib 和验证消息没有在传输过程中被改变的 hmac hashlib 哈希库模…...

四喜临门选股预警源码指标

{四喜临门选股预警} AP1:CROSS(MA(C,5),MA(C,10)); RSV:(CLOSE-LLV(LOW,9))/(HHV(HIGH,9)-LLV(LOW,9))*100; K:SMA(RSV,3,1); D:SMA(K,3,1); AP2:CROSS(K,D); DIFF:EMA(CLOSE,12) - EMA(CLOSE,26); DEA:EMA(DIFF,9); AP3:CROSS(DIFF,DEA); AP4:CROSS(MA(V,5),MA(V,10)); GYTJ1:…...

Kotlin新手教程五(扩展)

一、扩展 在Kotlin中可以给一个类添加一个新的方法而不用继承该类或者使用设计模式,这样的方法称为扩展。 1.扩展函数 声明一个扩展函数,我们需要用一个 接收者类型 也就是被扩展的类型来作为他的前缀。 下面代码为 MutableList 添加一个swap 函数&am…...

QT入门Containers之Widget、Frame

目录 一、QWidget界面相关 1、布局介绍 2、基本界面属性 3、特殊属性 二、QFrame 三、Demo展示 此文为作者原创,创作不易,转载请标明出处! 一、QWidget界面相关 1、布局介绍 为什么将QWidget容器放在第一个,因为目前使用过…...

数据结构与算法基础-学习-12-线性表之顺序队

一、个人理解队列是线性表的衍生之一,具有先进先出的特性,在队尾进行插入操作,在队头进行删除操作。队列的存储结构分为两个大类,一种是顺序队,就是用数组实现。另一种就是链队,使用链表实现。顺序队存在真…...

Python 字典(Dictionary)小窍门

字典是另一种可变容器模型,且可存储任意类型对象。字典的每个键值 key:value 对用冒号 : 分割,每个键值对之间用逗号 , 分割,整个字典包括在花括号 {} 中 ,格式如下所示:d {key1 : value1, key2 : value2 }注意:dict …...

知识图谱构建技术综述

摘要 *知识图谱为实现语义化智能搜索以及知识互联打下了基础,。, *随着知识的发展,传统的基于模板和规则构建的知识图谱已经被深度学习所替代。 知识组织得原则中:知识的充分性、有序性和标准化规则。深度学习的效果在很大程度上…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

GitHub 趋势日报 (2025年06月08日)

📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

【Oracle】分区表

个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...