每天一道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…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

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

Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...