每天一道leetcode:934. 最短的桥(图论中等广度优先遍历)
今日份题目:
给你一个大小为 n x n
的二元矩阵 grid
,其中 1
表示陆地,0
表示水域。
岛 是由四面相连的 1
形成的一个最大组,即不会与非组内的任何其他 1
相连。grid
中 恰好存在两座岛 。
你可以将任意数量的 0
变为 1
,以使两座岛连接起来,变成 一座岛 。
返回必须翻转的 0
的最小数目。
示例1
输入:grid = [[0,1],[1,0]] 输出:1
示例2
输入:grid = [[0,1,0],[0,0,0],[0,0,1]] 输出:2
示例3
输入:grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] 输出:1
提示
-
n == grid.length == grid[i].length
-
2 <= n <= 100
-
grid[i][j]
为0
或1
-
grid
中恰有两个岛
题目思路
分析题目,我们有两个岛屿,找一个岛到另一个岛的最小距离。找到其中一座岛,然后将其不断向外延伸一圈,直到到达了另一座岛,延伸的圈数即为最短距离。所以,第一步,我们要找到第一个岛屿;第二步,我们要从第一个岛屿的所有位置进行bfs搜索找到另一个岛。
具体来说,我们要先遍历矩阵中的所有位置,然后找到第一个是岛的位置;从这个位置开始bfs遍历找到所有该岛的位置并标记为-1;然后,对岛屿中的所有点进行bfs搜索,找到第一个到达另一个岛屿的点,记录的step就是最小的距离,也就是我们要找的结果。如果没有找到,就返回0(一般不会出现这种情况)。
注意:遍历过的点一定要标记,本题标记为-1,否则遍历周边时会回去。
代码
class Solution
{
public:int shortestBridge(vector<vector<int>>& grid) {int n=grid.size();int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //上下左右四个方向vector<pair<int, int> > island;queue<pair<int, int> > p;//遍历所有的点,找到第一个岛屿for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {//找到第一个岛屿,进行第一次bfs遍历if(grid[i][j]==1) {p.push({i,j});grid[i][j]=-1;//bfs获得第一个岛屿的完整位置while(!p.empty()) {auto [x,y]=p.front();p.pop();island.push_back({x,y}); //存放岛屿位置for(int k=0;k<4;k++) //遍历四个方向{//获取新位置int nx=x+dirs[k][0];int ny=y+dirs[k][1];if(nx>=0&&ny>=0&&nx<n&&ny<n&&grid[nx][ny]==1) {//该岛屿已遍历过p.push({nx,ny});grid[nx][ny]=-1; //标记为已到过}}}//将所有的岛屿加入到bfs队列中for(auto &&[x,y]:island) {p.push({x,y});}//从第一个岛屿的所有位置进行第二次bfs搜索找到第二个岛屿int step=0;while(!p.empty()) {int sz=p.size();for(int i=0;i<sz;i++) {auto [x,y]=p.front();p.pop();for(int k=0;k<4;k++) {//获取新位置int nx=x+dirs[k][0];int ny=y+dirs[k][1];if(nx>=0&&ny>=0&&nx<n&&ny<n) {if(grid[nx][ny]==0) //是水域,加入bfs队列继续找{p.push({nx,ny});grid[nx][ny]=-1; //标记为已到达过} //找到第二个岛屿了,返回步数else if(grid[nx][ny]==1) {return step;}}}}step++; //进行完一层bfs小搜索就加一}}}}return 0;}
};
提交结果
欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!
更新不易,宝子们点个赞支持下,谢谢!
相关文章:

每天一道leetcode:934. 最短的桥(图论中等广度优先遍历)
今日份题目: 给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。 岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 &#…...

【学习日记】【FreeRTOS】FreeRTOS 移植到 STM32F103C8
前言 本文基于野火 FreeRTOS 教程,内容是关于 FreeRTOS 官方代码的移植的注意事项,并将野火例程中 STM32F103RC 代码移植到 STM32F103C8。 一、FreeRTOS V9.0.0 源码的获取 两个下载链接: 官 网 代码托管 二、源码文件夹内容简介 Source…...

Qt 屏幕偶发性失灵
项目场景: 基于NXP i.mx7的Qt应用层项目开发,通过goodix使用触摸屏,走i2c协议。 问题描述 触摸屏使用过程中意外卡死,现场分为多种: i2c总线传输错误,直观表现为触摸屏无效,任何与触摸屏挂接在同一总线上的i2c设备,均受到干扰,并且在传输过程中内核报错以下代码: G…...

如何在pycharm中指定GPU
如何在pycharm中指定GPU 作者:安静到无声 个人主页 目录 如何在pycharm中指定GPU打开编辑配置点击环境变量添加GPU配置信息推荐专栏在Pycharm运行程序的时候,有时候需要指定GPU,我们可以采用以下方式进行设置: 打开编辑配置 点击环境变量 添加GPU配置信息 添加名称:CU…...
C#判断字符串中有没有字母,正则表达式、IsLetter
要判断字符串中是否包含字母,可以使用正则表达式或者循环遍历字符串的方式。 方法一:使用正则表达式 using System.Text.RegularExpressions;string input "Hello123"; bool containsLetter Regex.IsMatch(input, "[a-zA-Z]");上…...
Jtti:Ubuntu怎么限制指定端口和IP访问
在 Ubuntu 系统中,可以使用防火墙规则来限制特定的端口和IP访问。常用的防火墙管理工具是 iptables,以下是使用 iptables 来限制指定端口和IP访问的步骤: 安装 iptables: 如果系统中没有安装 iptables,可以使用以下命…...
机器学习/深度学习需要掌握的linux基础命令
很多深度学习/机器学习/数据分析等领域(或者说大多数在Python环境下进行操作的领域)的初学者入门时是在Windows上进行学习,也得益于如Anaconda等工具把环境管理做的如此友善 但如果想在该领域继续深耕,一定会与Linux操作系统打交…...
C++11 std::async推荐使用 std::launch::async 模式
async真假多线程 std::launch::async真多线程 std::launch::async | std::launch::deferred可能多线程 std::launch::deferred假多线程 枚举变量说明 枚举定义 enum class launch {async 1, // 0b1deferred 2, // 0b10any async | def…...
没有使用springboot 单独使用spring-boot-starter-logging
如果您不使用Spring Boot框架,但想单独使用Spring Boot Starter Logging,您可以按照以下步骤进行: 1. 添加Maven依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boo…...

创建Azure资源锁
锁的介绍 在Azure中,资源锁是一种用于保护订阅、资源组或者单个资源的机制。它可以防止对受锁定的资源进行删除或修改操作,帮助确保资源的连续可用性和安全性。 Azure中的资源锁可以分为两种类型: 删除锁(CanNotDelete…...
卷积神经网络教程 (CNN) – 使用 TensorFlow 在 Python 中开发图像分类器
在这篇博客中,让我们讨论什么是卷积神经网络 (CNN) 以及 卷积神经网络背后的架构——旨在解决 图像识别系统和分类问题。 卷积神经网络在图像和视频识别、推荐系统和自然语言处理方面有着广泛的应用。 目录 计算机如何读取图像? 为什么不是全连接网络?...
MyBatis XML映射处理CLOB和BLOB类型
Mybatis的MapperXML映射文件应该处理数据库字段类型为CLOB和BLOB类型的数据呢?首先我们先看下CLOB和BLOB这两种数据类型的介绍。 介绍 使用Mybatis时涉及到两种特殊类型的处理,分别是Blob(Binary Large Object)和Clob࿰…...

FPGA_学习_14_第一个自写模块的感悟和ila在线调试教程与技巧(寻找APD的击穿偏压)
前一篇博客我们提到了,如果要使用算法找到Vbr,通过寻找APD采集信号的噪声方差的剧变点去寻找Vbr是一个不错的方式。此功能的第一步是在FPGA中实现方差的计算,这个我们已经在上一篇博客中实现了。 继上一篇博客之后,感觉过了很久了…...

【2023新教程】树莓派定时自动拍照并上传腾讯云对象存储COS
1 换源 仅适用于Release date: May 3rd 2023、Debian version: 11 (bullseye)这个树莓派OS版本,其他版本不保证有效。 首先使用如下命令,查看自己树莓派的架构。 uname -a结果如下: 如果红圈处显示为aarch64,使用命令sudo na…...

校企合作谋发展 合作共赢谱新篇|云畅科技与湖南民族职业学院签订校企合作协议
产业是经济发展的重要引擎,人才是产业发展的重要资源。为积极探索软件人才培育新路径,共商政产学研协同新机制,8月8日,云畅科技与湖南省民族职业学院教育技术学院软件技术专业签订校企合作协议。 会上,学院副校长王志平…...

vue技术学习
vue快速入门 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>vue快速入门</title> </head> <body> <!--老师解读 1. div元素不是必须的,也可以是其它元素࿰…...

基于空间的图卷积神经网络:GNN
目录 欧氏空间中神经网络发挥巨大最作用,DNA,知识图谱三维或者多维空间不行 邻接矩阵实现图结构的矩阵化表示:造梦师 局和操作实现层内消息传递:带线的连接机传递消息 GCN通过邻域聚合实现特征提取 SVM支持向量机 编辑 硬分…...

.net core发布到IIS上出现 HTTP 错误 500.19
1.检查.net core 环境运行环境是否安装完成,类似如下环境 2.IIS是否安装全 本次原因就是IIS未安装全导致的 按照网上说的手动重启iis(iisreset)也不行...

01_Redis单线程与多线程
01——Redis单线程与多线程 一、Redis是单线程还是多线程 在谈Redis的单线程或多线程时,需要根据版本来区分。 在redis 3.x之前,redis是单线程的从redis 4.x开始,redis引入多线程。处理客户端请求时,使用单线程;在异…...
机器学习——随机森林【手动代码】
随机森林这个内容,是目前来说。。。最最最简单,最好理解,应该也是最好实现的了!!! 先挖坑,慢慢填 随机森林,这个名字取得,果然深得该算法的核心精髓,既随机&a…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...

通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...