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

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 算法原理

  1. 采用 BFS + 正难则反 的解题思想, 把所有为 0 的位置为起点, 把所有为 1 的位置为终点.
  2. 将所有为 0 的位置加入队列中, 一层一层往外扩, 将为 1 的位置, 修改为距离 0 的最短步数

细节点: 建立一个二维数组 int[][] distance, distinct[i][j] 中存的是 [i, j] 位置距离 0 的最短路径.

dest数组的作用:

  1. 不需使用 boolean 数组做标记 => 将原数组中为 1 的位置, 在 dest 中初始化为 -1(特殊标记)
  2. 不需使用 size 记录每层中元素个数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)
  3. 不需使用 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 进行入队操作
  2. 以边界上的 1 为起点, 进行多源 BFS, 将和其连通的其他的 1 进行标记.
  3. 最终, 返回内部未被标记的 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. 由于任意相邻的格子高度差 至多 为 1, 所以应以水域位置为起点(水域位置固定高度为 0), 进行多源 BFS
  2. 将水域位置加入队列, 一层一层往外扩展.
  3. 每扩展到一个位置, 这个位置上的高度, 应为上个位置的高度 +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 算法原理

  1. 依旧是 正难则反 + BFS

  2. 创建一个 dist 数值, 将陆地位置初始化为 0 

  3. 以陆地位置为起点, 向外扩展, 扩展到的海洋位置的值是原来位置的值的基础上 +1(dist[x][y] = dist[a][b] + 1)

  4. 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 矩阵 . - 力扣&#xff08;LeetCode&#xff09; 1.1 算法原理 采用 BFS 正难…...

基于Spring Boot+Vue的养老院管理系统【原创】

一.系统开发工具与环境搭建 1.系统设计开发工具 后端使用Java编程语言的Spring boot框架 项目架构&#xff1a;B/S架构 运行环境&#xff1a;win10/win11、jdk17 前端&#xff1a; 技术&#xff1a;框架Vue.js&#xff1b;UI库&#xff1a;ElementUI&#xff1b; 开发工具&…...

Linux screen和cscope工具使用总结

1 minicom使用 1.1 minicom配置 第一次启动时&#xff1a; 如果输入sudo minicom提示错误&#xff0c;则需&#xff1a; sudo minicom -s 启动 出现配置菜单&#xff1a;选serial port setup 进入串口配置 输入A配置串口驱动为/dev/ttyUSB0 输入E配置速率为115200 8N1 输入F将 …...

深度学习面试八股汇总

按序发布&#xff1a; 深度学习——优化算法、激活函数、归一化、正则化 进入 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 进入 深度学习——前向传播与反向传播、神经网络&#xff08;前馈神经网络与反馈神经网络&#xff09;、常见算法 进入 深度学习——卷积神…...

微服务架构面试内容整理-API 网关-Gateway

Spring Cloud Gateway 是一个用于构建 API 网关的框架,它为微服务架构提供了灵活的路由和过滤功能。作为 Spring Cloud 生态的一部分,Gateway 提供了易于使用的 API 和强大的功能,适合用于现代微服务架构中的请求管理和服务交互。以下是 Spring Cloud Gateway 的主要特点、工…...

22.04Ubuntu---ROS2使用rclcpp编写节点C++

节点需要存在于功能包当中&#xff0c;功能包需要存在于工作空间当中。 所以我们要想创建节点&#xff0c;就要先创建一个工作空间&#xff0c;再创建功能包。 第一步&#xff1a;创建工作空间 mkdir -p chapt2_ws/src/ 第二步&#xff1a;创建example_cpp功能包&#xff0c…...

XML 现实案例:深入解析与应用

XML 现实案例:深入解析与应用 XML(可扩展标记语言)自1998年成为W3C推荐标准以来,一直是数据交换和存储的重要工具。它是一种用于标记电子文件的结构化语言,使得数据不仅人类可读,而且机器可处理。本文将探讨XML在现实世界中的应用案例,展示其如何在不同领域中发挥作用。…...

Spring源码(十二):Spring MVC之Spring Boot

本篇将详细讨论Spring Boot 的启动/加载、处理请求的具体流程。我们先从一个简单的Spring Boot项目日志开始分析&#xff08;这里假设读者已经仔细阅读完了前面的文章&#xff0c;且对Spring源码有一定深度的了解&#xff0c;否则会看得一脸懵逼&#xff09;。 本文为2024重置…...

Kafka 之事务消息

前言&#xff1a; 在分布式消息系统中&#xff0c;事务消息也是一个热门课题&#xff0c;在项目的实际业务场景中&#xff0c;如果用到事务消息的场景也不少见&#xff0c;那 Kafka 作为一个高性能的分布式消息中间件&#xff0c;同样也支持事务消息&#xff0c;本篇我们将对 …...

小菜家教平台(四):基于SpringBoot+Vue打造一站式学习管理系统

前言 昨天配置完了过滤器&#xff0c;权限检验&#xff0c;基本的SpringSecurity功能已经配置的差不多了&#xff0c;今天继续开发&#xff0c;明天可能会暂停一天整理一下需求&#xff0c;然后就进行CRUD了。 今日进度 补充SpringSecurity异常处理和全局异常处理器 详细操作…...

解决 Vue3、Vite 和 TypeScript 开发环境下跨域的问题,实现前后端数据传递

引言 本文介绍如何在开发环境下解决 Vite 前端&#xff08;端口 3000&#xff09;和后端&#xff08;端口 80&#xff09;之间的跨域问题&#xff1a; 在开发环境中&#xff0c;前端使用的 Vite 端口与后端端口不一致&#xff0c;会产生跨域错误提示&#xff1a; Access to X…...

量化交易系统开发-实时行情自动化交易-3.3.数据采集流程

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来说说数据采集流程&#xff0c;后…...

探索PyAV:Python中的多媒体处理利器

文章目录 探索PyAV&#xff1a;Python中的多媒体处理利器第一部分&#xff1a;背景介绍第二部分&#xff1a;PyAV是什么&#xff1f;第三部分&#xff1a;如何安装PyAV&#xff1f;第四部分&#xff1a;简单的库函数使用方法1. 打开文件2. 查看流3. 遍历帧4. 编码帧5. 关闭输出…...

SpringBoot源码解析(三):启动开始阶段

SpringBoot源码系列文章 SpringBoot源码解析(一)&#xff1a;SpringApplication构造方法 SpringBoot源码解析(二)&#xff1a;引导上下文DefaultBootstrapContext SpringBoot源码解析(三)&#xff1a;启动开始阶段 目录 前言一、入口二、SpringApplicationRunListener1、作用…...

C# const与readonly关键字的区别

在C#中&#xff0c;readonly关键字用于定义在对象创建后不能更改的字段。它可以与常量(const)有些相似&#xff0c;但也有显著不同。以下是readonly关键字的一些关键点&#xff1a; 定义与用法&#xff1a; readonly字段可以在类的构造函数中初始化&#xff0c;而const字段必须…...

【数据分享】1901-2023年我国省市县镇四级的逐年降水数据(免费获取/Shp/Excel格式)

之前我们分享过1901-2023年1km分辨率逐月降水栅格数据和Shp和Excel格式的省市县四级逐月降水数据&#xff0c;原始的逐月降水栅格数据来源于彭守璋学者在国家青藏高原科学数据中心平台上分享的数据&#xff01;基于逐月数据我们采用求年累计值的方法得到逐年降水栅格数据&#…...

hhdb数据库介绍(9-4)

访问安全 权限体系 计算节点有两类用户&#xff0c;一类是计算节点数据库用户&#xff0c;用于操作数据&#xff0c;执行SELECT&#xff0c;UPDATE&#xff0c;DELETE&#xff0c;INSERT等SQL语句。另一类是关系集群数据库可视化管理平台用户&#xff0c;用于管理配置信息。此…...

苍穹外卖的分层所用到的技术以及工具+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(数列的极限为&#xff1a;,limit(s,n,oo))...

css:还是语法

emmet的使用 emmet是一个插件&#xff0c;Emmet 是 Zen Coding 的升级版&#xff0c;由 Zen Coding 的原作者进行开发&#xff0c;可以快速的编写 HTML、CSS 以及实现其他的功能。很多文本编辑器都支持&#xff0c;我们只是学会使用它&#xff1a; 生成html结构 <!-- emme…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...