BFS 算法专题(四):多源 BFS
目录
1. 01 矩阵
1.1 算法原理
1.2 算法代码
2. 飞地的数量
2.1 算法原理
2.2 算法代码
3. 地图中的最高点
3.1 算法原理
3.2 算法代码
4. 地图分析
4.1 算法原理
4.2 算法代码
1. 01 矩阵
. - 力扣(LeetCode)
1.1 算法原理
- 采用 BFS + 正难则反 的解题思想, 把所有为 0 的位置为起点, 把所有为 1 的位置为终点.
- 将所有为 0 的位置加入队列中, 一层一层往外扩, 将为 1 的位置, 修改为距离 0 的最短步数
细节点: 建立一个二维数组 int[][] distance, distinct[i][j] 中存的是 [i, j] 位置距离 0 的最短路径.
dest数组的作用:
- 不需使用 boolean 数组做标记 => 将原数组中为 1 的位置, 在 dest 中初始化为 -1(特殊标记)
- 不需使用 size 记录每层中元素个数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)
- 不需使用 step 记录扩展的层数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)

1.2 算法代码
class Solution {public int[][] updateMatrix(int[][] mat) {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m = mat.length, n = mat[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(mat[i][j] == 0) q.offer(new int[]{i, j});else dist[i][j] = -1;}}// 以为 0 位置为起点, 一层一层往外扩while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});}}}return dist;}
}
2. 飞地的数量
. - 力扣(LeetCode)
2.1 算法原理
正难则反 + 多源 BFS
- 将边界上的 1 进行入队操作
- 以边界上的 1 为起点, 进行多源 BFS, 将和其连通的其他的 1 进行标记.
- 最终, 返回内部未被标记的 1 的个数

2.2 算法代码
class Solution {public int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check = new boolean[m][n];Queue<int[]> q = new LinkedList<>();// 将边界上的 1 入队列for(int i = 0; i < m; i++) {if(grid[i][0] == 1) q.offer(new int[]{i, 0});if(grid[i][n - 1] == 1) q.offer(new int[]{i, n - 1});}for(int j = 0; j < n; j++) {if(grid[0][j] == 1) q.offer(new int[]{0, j});if(grid[m - 1][j] == 1) q.offer(new int[]{m - 1, j});}// 多源 BFS: 将和边界上连通的 1 进行标记while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];check[a][b] = true;for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y]) {check[x][y] = true;q.offer(new int[]{x, y});}}}// 统计内部不连通的 1 的个数int ret = 0;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) if(grid[i][j] == 1 && !check[i][j]) ret++;}return ret;}
}
3. 地图中的最高点
. - 力扣(LeetCode)
3.1 算法原理
- 由于任意相邻的格子高度差 至多 为 1, 所以应以水域位置为起点(水域位置固定高度为 0), 进行多源 BFS
- 将水域位置加入队列, 一层一层往外扩展.
- 每扩展到一个位置, 这个位置上的高度, 应为上个位置的高度 +1(求最高高度, 要求高度差不超过 1)

3.2 算法代码
class Solution {public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] height = new int[m][n];for(int i = 0; i < m; i++) Arrays.fill(height[i], -1);Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(isWater[i][j] == 1) {height[i][j] = 0;q.offer(new int[]{i, j});}}}int[] dx = {1, -1, 0, 0};int[] dy = {0, 0 ,1, -1};while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1) {height[x][y] = height[a][b] + 1;q.offer(new int[]{x, y});}}}return height;}
}
4. 地图分析
. - 力扣(LeetCode)
4.1 算法原理
-
依旧是 正难则反 + BFS
-
创建一个 dist 数值, 将陆地位置初始化为 0
-
以陆地位置为起点, 向外扩展, 扩展到的海洋位置的值是原来位置的值的基础上 +1(dist[x][y] = dist[a][b] + 1)
-
dist 数组中的最大值, 就是海洋距离陆地的最远位置
4.2 算法代码
class Solution {public int maxDistance(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) Arrays.fill(dist[i], -1);// 将陆地在 dist 中的位置初始化为 0// 并入队boolean sea = false;boolean ground = false;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1) {dist[i][j] = 0;q.offer(new int[]{i, j});}if(grid[i][j] == 0) sea = true;if(grid[i][j] == 1) ground =true;}}if(!sea || !ground) return -1;int[] dx = {1, -1, 0, 0};int[] dy = {0 ,0 , 1, -1};int ret = 0;while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});ret = Math.max(ret, dist[x][y]);}}}return ret;}
}
END
相关文章:
BFS 算法专题(四):多源 BFS
目录 1. 01 矩阵 1.1 算法原理 1.2 算法代码 2. 飞地的数量 2.1 算法原理 2.2 算法代码 3. 地图中的最高点 3.1 算法原理 3.2 算法代码 4. 地图分析 4.1 算法原理 4.2 算法代码 1. 01 矩阵 . - 力扣(LeetCode) 1.1 算法原理 采用 BFS 正难…...
基于Spring Boot+Vue的养老院管理系统【原创】
一.系统开发工具与环境搭建 1.系统设计开发工具 后端使用Java编程语言的Spring boot框架 项目架构:B/S架构 运行环境:win10/win11、jdk17 前端: 技术:框架Vue.js;UI库:ElementUI; 开发工具&…...
Linux screen和cscope工具使用总结
1 minicom使用 1.1 minicom配置 第一次启动时: 如果输入sudo minicom提示错误,则需: sudo minicom -s 启动 出现配置菜单:选serial port setup 进入串口配置 输入A配置串口驱动为/dev/ttyUSB0 输入E配置速率为115200 8N1 输入F将 …...
深度学习面试八股汇总
按序发布: 深度学习——优化算法、激活函数、归一化、正则化 进入 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 进入 深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法 进入 深度学习——卷积神…...
微服务架构面试内容整理-API 网关-Gateway
Spring Cloud Gateway 是一个用于构建 API 网关的框架,它为微服务架构提供了灵活的路由和过滤功能。作为 Spring Cloud 生态的一部分,Gateway 提供了易于使用的 API 和强大的功能,适合用于现代微服务架构中的请求管理和服务交互。以下是 Spring Cloud Gateway 的主要特点、工…...
22.04Ubuntu---ROS2使用rclcpp编写节点C++
节点需要存在于功能包当中,功能包需要存在于工作空间当中。 所以我们要想创建节点,就要先创建一个工作空间,再创建功能包。 第一步:创建工作空间 mkdir -p chapt2_ws/src/ 第二步:创建example_cpp功能包,…...
XML 现实案例:深入解析与应用
XML 现实案例:深入解析与应用 XML(可扩展标记语言)自1998年成为W3C推荐标准以来,一直是数据交换和存储的重要工具。它是一种用于标记电子文件的结构化语言,使得数据不仅人类可读,而且机器可处理。本文将探讨XML在现实世界中的应用案例,展示其如何在不同领域中发挥作用。…...
Spring源码(十二):Spring MVC之Spring Boot
本篇将详细讨论Spring Boot 的启动/加载、处理请求的具体流程。我们先从一个简单的Spring Boot项目日志开始分析(这里假设读者已经仔细阅读完了前面的文章,且对Spring源码有一定深度的了解,否则会看得一脸懵逼)。 本文为2024重置…...
Kafka 之事务消息
前言: 在分布式消息系统中,事务消息也是一个热门课题,在项目的实际业务场景中,如果用到事务消息的场景也不少见,那 Kafka 作为一个高性能的分布式消息中间件,同样也支持事务消息,本篇我们将对 …...
小菜家教平台(四):基于SpringBoot+Vue打造一站式学习管理系统
前言 昨天配置完了过滤器,权限检验,基本的SpringSecurity功能已经配置的差不多了,今天继续开发,明天可能会暂停一天整理一下需求,然后就进行CRUD了。 今日进度 补充SpringSecurity异常处理和全局异常处理器 详细操作…...
解决 Vue3、Vite 和 TypeScript 开发环境下跨域的问题,实现前后端数据传递
引言 本文介绍如何在开发环境下解决 Vite 前端(端口 3000)和后端(端口 80)之间的跨域问题: 在开发环境中,前端使用的 Vite 端口与后端端口不一致,会产生跨域错误提示: Access to X…...
量化交易系统开发-实时行情自动化交易-3.3.数据采集流程
19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来说说数据采集流程,后…...
探索PyAV:Python中的多媒体处理利器
文章目录 探索PyAV:Python中的多媒体处理利器第一部分:背景介绍第二部分:PyAV是什么?第三部分:如何安装PyAV?第四部分:简单的库函数使用方法1. 打开文件2. 查看流3. 遍历帧4. 编码帧5. 关闭输出…...
SpringBoot源码解析(三):启动开始阶段
SpringBoot源码系列文章 SpringBoot源码解析(一):SpringApplication构造方法 SpringBoot源码解析(二):引导上下文DefaultBootstrapContext SpringBoot源码解析(三):启动开始阶段 目录 前言一、入口二、SpringApplicationRunListener1、作用…...
C# const与readonly关键字的区别
在C#中,readonly关键字用于定义在对象创建后不能更改的字段。它可以与常量(const)有些相似,但也有显著不同。以下是readonly关键字的一些关键点: 定义与用法: readonly字段可以在类的构造函数中初始化,而const字段必须…...
【数据分享】1901-2023年我国省市县镇四级的逐年降水数据(免费获取/Shp/Excel格式)
之前我们分享过1901-2023年1km分辨率逐月降水栅格数据和Shp和Excel格式的省市县四级逐月降水数据,原始的逐月降水栅格数据来源于彭守璋学者在国家青藏高原科学数据中心平台上分享的数据!基于逐月数据我们采用求年累计值的方法得到逐年降水栅格数据&#…...
hhdb数据库介绍(9-4)
访问安全 权限体系 计算节点有两类用户,一类是计算节点数据库用户,用于操作数据,执行SELECT,UPDATE,DELETE,INSERT等SQL语句。另一类是关系集群数据库可视化管理平台用户,用于管理配置信息。此…...
苍穹外卖的分层所用到的技术以及工具+jwt令牌流程图(jwt验证)
分层用到的技术以及工具: jwt令牌流程图:...
Python——数列1/2,2/3,3/4,···,n/(n+1)···的一般项为Xn=n/(n+1),当n—>∞时,判断数列{Xn}是否收敛
没注释的源代码 from sympy import * n symbols(n) s n/(n1) print(数列的极限为:,limit(s,n,oo))...
css:还是语法
emmet的使用 emmet是一个插件,Emmet 是 Zen Coding 的升级版,由 Zen Coding 的原作者进行开发,可以快速的编写 HTML、CSS 以及实现其他的功能。很多文本编辑器都支持,我们只是学会使用它: 生成html结构 <!-- emme…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
