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

C++优选算法十七 多源BFS

1.单源最短路问题

一个起点一个终点。

定义:在给定加权图中,选择一个顶点作为源点,计算该源点到图中所有其他顶点的最短路径长度。

2.多源最短路问题

定义:多源最短路问题指的是在图中存在多个起点,需要求出从这些起点到图中所有其他顶点的最短路径。

3.多源BFS

用BFS解决边权为1的多源最短路问题。

解法一:

        暴力解法,把多源最短路问题转化为若干个单源最短路问题。

解法二:

        把所有的源点变成一个“超级源点”,问题就变成了单一的单源最短路问题。

  1. 把所有的起点加入到队列里面。
  2. 一层一层的往外扩展。

4.例题

4.1 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]

示例 2:

输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]]

解法(bfs)(多个源头的最短路问题)
算法思路:

对于求的最终结果,我们有两种方式:
第一种方式:从每一个 1开始,然后通过层序遍历找到离它最近的0。
这一种方式,我们会以所有的 1 起点,来一次层序遍历,势必会遍历到很多重复的点。并且如果矩阵中只有一个 0 的话,每一次层序遍历都要遍历很多层,时间复杂度较高。

换一种方式:从 0开始层序遍历,并且记录遍历的层数。当第一次碰到1的时候,当前的层数就是这个 1 离 0 的最短距离。
这一种方式,我们在遍历的时候标记一下处理过的 1,能够做到只用遍历整个矩阵一次,就能得到最终结果。
但是,这里有一个问题,0是有很多个的,我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢?
其实很简单,我们可以先把所有的 0 都放在队列中,把它们当成一个整体,每次把当前队列里面的所有元素向外扩展一次。

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {queue<PII> qe;int m=mat.size();int n=mat[0].size();//vv[i][j]==-1 表示没有搜索过//vv[i][j]!=-1 表示最短距离vector<vector<int>> vv(m,vector<int>(n,-1));//把所有的源点加入队列for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j]==0){qe.push({i,j});vv[i][j]=0;}}}//一层一层往外扩展while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){vv[x][y]=vv[a][b]+1;qe.push({x,y});}}}return vv;}
};

4.2 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1:

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

示例 2:

输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。

解法:
算法思路:
        正难则反:

从边上的 1开始搜索,把与边上1相连的联通区域全部标记一下;
然后再遍历一遍矩阵,看看哪些位置的1没有被标记即可。
        标记的时候,可以用「多源 bfs」解决。 

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:int numEnclaves(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();queue<PII> qe;vector<vector<bool>> vv(m,vector<bool>(n,false));//将边上的1加入到队列中for(int i=0;i<m;i++){if(grid[i][0]==1)qe.push({i,0});if(grid[i][n-1]==1)qe.push({i,n-1});}for(int j=0;j<n;j++){if(grid[0][j]==1)qe.push({0,j});if(grid[m-1][j]==1)qe.push({m-1,j});}while(qe.size()){auto [a,b]=qe.front();qe.pop();vv[a][b]=true;for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!vv[x][y]&&grid[x][y]==1){qe.push({x,y});vv[x][y]=true;}}}int count=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&vv[i][j]==false)count++;}}return count;}
};

4.3 地图中的最高点

给你一个大小为 m x n 的整数矩阵 isWater ,它代表了一个由 陆地 和 水域 单元格组成的地图。

  • 如果 isWater[i][j] == 0 ,格子 (i, j) 是一个 陆地 格子。
  • 如果 isWater[i][j] == 1 ,格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度:

  • 每个格子的高度都必须是非负的。
  • 如果一个格子是 水域 ,那么它的高度必须为 0 。
  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着,就称它们为相邻的格子。(也就是说它们有一条公共边)

找到一种安排高度的方案,使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ,其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法,请返回 任意一个 。

示例 1:

输入:isWater = [[0,1],[0,0]]
输出:[[1,0],[2,1]]
解释:上图展示了给各个格子安排的高度。
蓝色格子是水域格,绿色格子是陆地格。

示例 2:

输入:isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出:[[1,1,0],[0,1,1],[1,2,2]]
解释:所有安排方案中,最高可行高度为 2 。
任意安排方案中,只要最高高度为 2 且符合上述规则的,都为可行方案。

解法:直接使用多源BFS。

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int m=isWater.size();int n=isWater[0].size();vector<vector<int>> vv(m,vector<int>(n,-1));queue<PII> qe;//把所有的源点加入队列中for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]==1){vv[i][j]=0;qe.push({i,j});}}}while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){qe.push({x,y});vv[x][y]=vv[a][b]+1;}}}return vv;}
};

 4.4 地图分析

你现在手里有一份大小为 n x n 的 网格 grid,上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。

请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的,并返回该距离。如果网格上只有陆地或者海洋,请返回 -1

我们这里说的距离是「曼哈顿距离」( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1:

输入:grid = [[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释: 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大,最大距离为 2。

示例 2:

输入:grid = [[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释: 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大,最大距离为 4。

解法:01矩阵的变形题,直接上多源BFS。

class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:int maxDistance(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();queue<PII> qe;vector<vector<int>> vv(m,vector<int>(n,-1));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){vv[i][j]=0;qe.push({i,j});}}}while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){qe.push({x,y});vv[x][y]=vv[a][b]+1;}}}int ret=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){ret=max(ret,vv[i][j]);}}if(ret==0)return -1;return ret;}
};

相关文章:

C++优选算法十七 多源BFS

1.单源最短路问题 一个起点一个终点。 定义&#xff1a;在给定加权图中&#xff0c;选择一个顶点作为源点&#xff0c;计算该源点到图中所有其他顶点的最短路径长度。 2.多源最短路问题 定义&#xff1a;多源最短路问题指的是在图中存在多个起点&#xff0c;需要求出从这些…...

Mongodb入门到放弃

Mongodb分片概括 分片在多台服务器上分布数据的方法&#xff0c; Mongodb使用分片来支持具有非常大的数据集和高吞吐量的操作的部署 具有大数据集和高吞吐量应用程序的数据库系统&#xff0c;可以挑战单台服务器的容量。 例如&#xff0c;高查询率可以耗尽服务器的cpu容量&…...

青藤云安全携手财信证券,入选金融科技创新应用优秀案例

11月29日&#xff0c;由中国信息通信研究院主办的第四届“金信通”金融科技创新应用案例评选结果正式发布。财信证券与青藤云安全联合提交的“基于RASP技术的API及数据链路安全治理项目”以其卓越的创新性和先进性&#xff0c;成功入选金融科技创新应用优秀案例。 据悉&#x…...

在CentOS系统中安装工具包的时候报错的解决方法

我刚装了一个新的虚拟机&#xff0c;打算安装一些工具出现了错误信息 执行的命令如下&#xff1a; yum install -y yum-utils device-mapper-persistent-data lvm2错误信息如下 Cannot find a valid baseurl for repo: base/7/x86_64搜索了一下原因有好几种。 一是网络不通…...

cad软件打不开报错cad acbrandres dll加载失败

一切本来很顺利哒 但是&#xff0c;当我用快捷方式打开时&#xff0c;就出现了这个错误。进入文件路径&#xff0c;是有这个的&#xff1b; 在文件路径直接打开&#xff0c;也会提示错误 原因竟然是我改了个名字&#xff1a; 随便选的文件路径&#xff0c;空的,文件名为Acr…...

14、保存与加载PyTorch训练的模型和超参数

文章目录 1. state_dict2. 模型保存3. check_point4. 详细保存5. Docker6. 机器学习常用库 1. state_dict nn.Module 类是所有神经网络构建的基类&#xff0c;即自己构建一个深度神经网络也是需要继承自nn.Module类才行&#xff0c;并且nn.Module中的state_dict包含神经网络中…...

【前端开发】JS+Vuew3请求列表数据并分页

应用技术&#xff1a;原生JavaScript Vue3 $(function () {ini(); });function ini() {const { createApp, ref, onMounted } Vue;createApp({setup() {const data ref({studentList: [],page: 1,pageSize: 10,});const getStudentList async (page, key) > {window.ons…...

Trimble X12助力电力管廊数据采集,为机器人巡视系统提供精准导航支持

地下电缆是一个城市重要的基础设施&#xff0c;它不仅具有规模大、范围广、空间分布复杂等特点&#xff0c;更重要的是它还承担着信息传输、能源输送等与人们生活息息相关的重要功能&#xff0c;也是一个城市赖以生存和发展的物质基础。 01、项目概述 本次项目是对某区域2公里左…...

Docker 清理镜像策略详解

文章目录 前言一、删除 Docker 镜像1. 查看当前镜像2. 删除单个镜像3. 删除多个镜像4. 删除所有未使用的镜像5. 删除悬空的 Docker 镜像6. 根据模式删除镜像7. 删除所有镜像 二、删除 Docker 容器1. 查找容器2. 删除一个或多个特定容器3. 退出时删除容器4. 删除所有已退出的容器…...

【Linux】TCP网络编程

目录 V1_Echo_Server V2_Echo_Server多进程版本 V3_Echo_Server多线程版本 V3-1_多线程远程命令执行 V4_Echo_Server线程池版本 V1_Echo_Server TcpServer的上层调用如下&#xff0c;和UdpServer几乎一样&#xff1a; 而在InitServer中&#xff0c;大部分也和UDP那里一样&…...

排序学习整理(2)

上集回顾 排序学习整理&#xff08;1&#xff09;-CSDN博客 2.3 交换排序 交换排序的基本思想是&#xff1a;根据序列中两个记录键值的比较结果&#xff0c;交换这两个记录在序列中的位置。 特点&#xff1a; 通过比较和交换操作&#xff0c;将键值较大的记录逐步移动到序列…...

AI蛋白质设计与人工智能药物设计

AI蛋白质设计与人工智能药物设计 AI蛋白质设计 一、蛋白质相关的深度学习简介 1.基础概念 1.1.机器学习简介&#xff1a;从手写数字识别到大语言模型 1.2.蛋白质结构预测与设计回顾 1.3.Linux简介 1.4.代码环境&#xff1a;VS code和Jupyter notebook* 1.5.Python关键概…...

IOS ARKit进行图像识别

先讲一下基础控涧&#xff0c;资源的话可以留言&#xff0c;抽空我把它传到GitHub上&#xff0c;这里没写收积分&#xff0c;竟然充值才能下载&#xff0c;我下载也要充值&#xff0c;牛&#xff01; ARSCNView 可以理解画布或者场景 1 配置 ARWorldTrackingConfiguration AR追…...

初级数据结构——二叉搜索树

目录 前言一、定义二、基本操作三、时间复杂度分析四、变体五、动态图解六、代码模版七、经典例题[1.——700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/)代码题解 [2.——938. 二叉搜索树的范围和](https://leetcode.cn/problems/ra…...

C++设计模式之组合模式中如何实现同一层部件的有序性

在组合模式中&#xff0c;为了实现同一层上部件的有序性&#xff0c;可以采取以下几种设计方法&#xff1a; 1. 使用有序集合 使用有序集合&#xff08;如 std::list、std::vector 或其他有序容器&#xff09;来存储和管理子部件。这种方法可以确保子部件按照特定顺序排列&am…...

duxapp RN 端使用AppUpgrade 进行版本更新

版本更新包含了组件和工具的组合 注册 下面这是 duxcms 入口文件检查更新的注册方法&#xff0c;注册的同时会检查更新 import {request,updateApp,userConfig } from ./utils// 检查app更新 setTimeout(async () > {if (process.env.TARO_ENV rn) {// eslint-disable-n…...

【计网】自定义序列化反序列化(三) —— 实现网络版计算器【下】

&#x1f30e;实现网络版计算器【下】 本次序列化与反序列化所用到的代码&#xff0c;Tcp服务自定义序列化反序列化实现网络版计算器。 文章目录&#xff1a; 实实现网络版计算器【下】 客户端实现     基于守护进程的改写 &#x1f680;客户端实现 在这之前&#xff0c…...

神经网络中的优化方法(一)

目录 摘要Abstract1. 与纯优化的区别1.1 经验风险最小化1.2 代理损失函数1.3 批量算法和小批量算法 2. 神经网络中优化的挑战2.1 病态2.2 局部极小值2.3 高原、鞍点和其他平坦区域2.4 悬崖和梯度爆炸2.5 长期依赖2.6 非精确梯度2.7 局部和全局结构间的弱对应 3. 基本算法3.1 随…...

Linux 计算机网络基础概念

目录 0.前言 1.计算机网络背景 1.1 独立模式 1.2 网络互联 1.3 局域网&#xff08;Local Area Network&#xff0c;LAN&#xff09; 1.4 广域网&#xff08;Wide Area Network&#xff0c;WAN&#xff09; 2.协议 2.1什么是协议 2.2协议分层和软件分层 2.3 OSI七层网络模型 2.3…...

qt QGraphicsEllipseItem详解

1、概述 QGraphicsEllipseItem是Qt框架中QGraphicsItem的一个子类&#xff0c;它提供了一个可以添加到QGraphicsScene中的椭圆项。QGraphicsEllipseItem表示一个带有填充和轮廓的椭圆&#xff0c;也可以用于表示椭圆段&#xff08;通过startAngle()和spanAngle()方法&#xff…...

Python websocket

router.websocket(/chat/{flow_id}) 接口代码&#xff0c;并了解其工作流程、涉及的组件以及如何基于此实现你的新 WebSocket 接口。以下内容将分为几个部分进行讲解&#xff1a; 接口整体概述代码逐行解析关键组件和依赖关系如何基于此实现新功能示例&#xff1a;创建一个新的…...

【MySQL-5】MySQL的内置函数

目录 1. 整体学习的思维导图 2. 日期函数 ​编辑 2.1 current_date() 2.2 current_time() 2.3 current_timestamp() 2.4 date(datetime) 2.5 now() 2.6 date_add() 2.7 date_sub() 2.8 datediff() 2.9 案例 2.9.1 创建一个出生日期登记簿 2.9.2 创建一个留言版 3…...

深度学习笔记之BERT(三)RoBERTa

深度学习笔记之RoBERTa 引言回顾&#xff1a;BERT的预训练策略RoBERTa训练过程分析静态掩码与动态掩码的比较模型输入模式与下一句预测使用大批量进行训练使用Byte-pair Encoding作为子词词元化算法更大的数据集和更多的训练步骤 RoBERTa配置 引言 本节将介绍一种基于 BERT \t…...

C++知识点总结(59):背包型动态规划

背包型动态规划 一、背包 dp1. 01 背包&#xff08;限量&#xff09;2. 完全背包&#xff08;不限量&#xff09;3. 口诀 二、例题1. 和是质数的子集数2. 黄金的太阳3. 负数子集和4. NASA的⻝物计划 一、背包 dp 1. 01 背包&#xff08;限量&#xff09; 假如有这几个物品&am…...

C++:反向迭代器的实现

反向迭代器的实现与 stack 、queue 相似&#xff0c;是通过适配器模式实现的。通过传入不同类型的迭代器来实现其反向迭代器。 正向迭代器中&#xff0c;begin() 指向第一个位置&#xff0c;end() 指向最后一个位置的下一个位置。 代码实现&#xff1a; template<class I…...

webGL入门教程_04vec3、vec4 和齐次坐标总结

vec3、vec4 和齐次坐标总结 1. vec3 和 vec4 1.1 什么是 vec3 和 vec4&#xff1f; vec3&#xff1a; GLSL 中的三维向量类型&#xff0c;包含 3 个浮点数&#xff1a;(x, y, z)。常用于表示三维坐标、RGB 颜色、法线、方向等。 vec4&#xff1a; GLSL 中的四维向量类型&…...

uniapp中父组件数组更新后与页面渲染数组不一致实战记录

简单描述一下业务场景方便理解: 商品设置功能,支持添加多组商品(点击添加按钮进行增加).可以对任意商品进行删除(点击减少按钮对选中的商品设置进行删除). 问题: 正常添加操作后,对已添加的任意商品删除后,控制台打印数组正常.但是与页面显示不一致.已上图为例,选中尾…...

优化 Conda 下载速度:详细的代理配置和网络管理策略

优化 Conda 下载速度&#xff1a;详细的代理配置和网络管理策略 为了彻底解决使用 Conda 下载 PyTorch 时遇到的速度问题&#xff0c;并确保下载过程稳定可靠&#xff0c;这需要一个详细、综合的技术方案。让我们更深入地分析问题原因&#xff0c;然后详尽地解释采取的解决策略…...

服务器遭受DDoS攻击后如何恢复运行?

当服务器遭受 DDoS&#xff08;分布式拒绝服务&#xff09;攻击 后&#xff0c;恢复运行需要快速采取应急措施来缓解攻击影响&#xff0c;并在恢复后加强防护以减少未来攻击的风险。以下是详细的分步指南&#xff1a; 一、应急处理步骤 1. 确认服务器是否正在遭受 DDoS 攻击 …...

MFC音视频播放器-支持电子放大等功能

前言 本播放器在VS2019下开发&#xff0c;使用ffmpegD3D实现视频播放渲染功能。同时本播放器支持录像功能、截图功能、音视频播放功能、码流信息显示、电子放大功能等。D3D的渲染同时支持surface和texture两种方式&#xff0c;电子放大功能是在D3D Texture方式下进行实现。以下…...

如何建设和优化一个网站/百度开户返点

相比LCS的组策略&#xff0c;OCS增加了很多功能。做为IT人员管理和实施人员统一部署的好助手&#xff0c;它的一些功能非常有用&#xff0c;比如保存用户密码、设置通讯薄URL和限制用户添加数量等&#xff0c;有效的扩展和补充了了OCS控制台的现有功能而不必再做二次开发。策略…...

自助建站系统源码下载/开源crm系统

联想thinkpad e580笔记本网卡驱动是款不错的lenovo系列的驱动程序&#xff0c;如果您的联想笔记本出现无法识别网卡驱动或网络卡顿等情况&#xff0c;可以来本站下载此e580网卡驱动帮助您有效的解决相关问题等&#xff0c;欢迎有需要的用户前来下载&#xff01;联想e580网卡驱动…...

wordpress网易云音乐自定义css/阿里指数官网最新版本

关注并标星百问科技嵌入式干货&#xff0c;第一时间送达------感谢各位耐心等候。昨天更新蓝牙第4节&#xff1a;009.蓝牙系统从零讲解/第02课_BLE协议栈/第03节_BLE协议各层数据格式概述 &#xff0c;这节依然免费试看&#xff0c;下一节开始加密收费。主讲&#xff1a;BLE协议…...

宁波网站优化平台/营销案例最新

1&#xff0c;确定性策略梯度 1.1&#xff0c;基本概念 随机性策略梯度算法被广泛应用于解决大型动作空间或者连续动作空间的强化学习问题。其基本思想是将策略表示成以 为参数的策略函数 。基于采样数据&#xff0c;通过调整参数 使得最终的累计回报最大。即&#xff1a;通…...

郑州做的比较好网站公司吗/搜索引擎免费登录入口

【100个】计算机理论英文参考文献供您参考,希望能解决毕业生们的计算机理论论文参考文献哪里找相关问题,整理好参考文献那就开始写计算机理论论文吧&#xff01;一、计算机理论论文参考文献范文[1]抑制OFDM信号峰均比的PTS算法分析与优化.胡茂凯.陈西宏.刘强&#xff0c;2011陕…...

辽宁做网站/windows优化大师使用方法

滚动条的组成&#xff1a; ::-webkit-scrollbar //滚动条整体部分 ::-webkit-scrollbar-thumb // 滚动条里面的小方块&#xff0c;能上下左右移动&#xff08;取决于是垂直滚动条还是水平滚动条&#xff09; ::-webkit-scrollbar-track //滚动条的轨道…...