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

BFS解决多源最短路相关leetcode算法题

文章目录

  • 1.01矩阵
  • 2.飞地的数量
  • 3.地图中的最高点
  • 4.地图分析

1.01矩阵

01矩阵
)

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {//正难则反,找0到1的最短距离int m = mat.size(),n = mat[0].size();queue<pair<int,int>> q;//通过此数组对应位置的值既可以标识某个位置是否已访问过,也可在此基础上往外扩展vector<vector<int>> dist(m,vector<int>(n,-1));//if(dist[][] == -1) 表示此位置没被访问过//if(dist[][] != -1) 表示此位置被访问过for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j] == 0){dist[i][j] = 0;q.push({i,j});}}}while(q.size()){auto [a,b] = q.front();q.pop();for(int i=0;i<4;i++){int x = a+dx[i], y =b+dy[i];if(x>=0 && x<m && y>=0 && y<n && mat[x][y]&& dist[x][y]==-1){dist[x][y] = dist[a][b]+1;q.push({x,y});}}}return dist;}
};

2.飞地的数量

飞地的数量
在这里插入图片描述

class Solution {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(),n = grid[0].size();vector<vector<bool>> vis(m,vector<bool>(n));queue<pair<int,int>> q;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i==0||i==m-1||j==0||j==n-1){if(grid[i][j] == 1){q.push({i,j});vis[i][j] = true;}}}}//多源BFSwhile(q.size()){auto [a,b] = q.front();q.pop();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&& !vis[x][y]){q.push({x,y});vis[x][y] = true;}}}//遍历统计int ret = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1 && !vis[i][j]) ret++;}}return ret;}
};

3.地图中的最高点

地图中的最高点
在这里插入图片描述

class Solution {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(), n=isWater[0].size();queue<pair<int,int>> q;vector<vector<int>> dist(m,vector<int>(n,-1));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]){q.push({i,j});dist[i][j]=0;}}}//多源BFSwhile(q.size()){auto [a,b] = q.front();q.pop();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.push({x,y});}}}return dist;}
};

4.地图分析

地图分析
在这里插入图片描述

class Solution {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(),n=grid[0].size();vector<vector<int>> dist(m,vector<int>(n,-1));queue<pair<int,int>> q;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]){dist[i][j] =0;q.push({i,j});}}}//多源BFSint ret = -1;while(q.size()){auto[a,b] = q.front();q.pop();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.push({x,y});ret = max(ret,dist[x][y]);}}}return ret;}
};

相关文章:

BFS解决多源最短路相关leetcode算法题

文章目录 1.01矩阵2.飞地的数量3.地图中的最高点4.地图分析 1.01矩阵 01矩阵 class Solution {int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0}; public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {//正难则反&#xff0c;找0…...

ARM GIC(四) gicv3架构基础

GICv3架构是GICv2架构的升级版&#xff0c;增加了很多东西。变化在于以下&#xff1a; 使用属性层次&#xff08;affinity hierarchies&#xff09;&#xff0c;来对core进行标识&#xff0c;使gic支持更多的core 将cpu interface独立出来&#xff0c;用户可以将其设计在core…...

Kafka日志

位置 server.properties配置文件中通过log.dir指定日志存储目录 log.dir/{topic}-{partition} 核心文件 .log 存储消息的日志文件&#xff0c;固定大小为1G&#xff0c;写满后会新增一个文件&#xff0c;文件名表示当前日志文件记录的第一条消息的偏移量。 .index 以偏移…...

gitattributes配置文件的作用

0 Preface/Foreword 0.1 基本概念 Git版本管控工具功能强大&#xff0c;在使用过程中&#xff0c;在多人合作的项目开发过程中&#xff0c;经常会遇到提交代码时出现的warning提醒&#xff0c;尤其是换行符。 Linux/Unix/Mac OS操作系统的换行符使用LF符号&#xff08;\n&am…...

【华为鸿蒙系统学习】- 如何利用鸿蒙系统进行App项目开发|自学篇

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 &#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 创建鸿蒙第一个App项目 项目创建 工程目录区 预览区 运行Hello World 基本工程目录 ws:工程…...

基于SpringBoot的足球社区管理系统

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于SpringBoot的足球社区管理系统,java…...

ubuntu22.04上安装charles-proxy

在 Ubuntu 22.04 上安装 .tar.gz 格式的 Charles Proxy (charles-proxy-4.6.5_amd64.tar.gz) 需要解压缩文件并运行其中的安装脚本或可执行文件。以下是具体步骤&#xff1a; 1. 下载文件 假设你已经从 Charles Proxy 官网下载了 charles-proxy-4.6.5_amd64.tar.gz 文件。 2…...

(2021|CVPR,XMC-GAN,对比学习,注意力自调制)用于文本到图像生成的跨模态对比学习

Cross-Modal Contrastive Learning for Text-to-Image Generation 公众&#xff1a;EDPJ&#xff08;添加 VX&#xff1a;CV_EDPJ 或直接进 Q 交流群&#xff1a;922230617 获取资料&#xff09; 目录 0. 摘要 1. 简介 2. 相关工作 3. 基础 4. 方法 4.1 用于文本到图像…...

【Linux基本命令】

文章目录 一. Linux基本命令第三回二. 结束语 一. Linux基本命令第三回 cal指令&#xff0c;命令格式&#xff1a;cal 【参数】【月份】【年份】 功能&#xff0c;用于查看日历等时间信息&#xff0c;如只有一个参数&#xff0c;则表示年份&#xff0c;有两个参数则表示月份和…...

Wi-Fi、蓝牙、ZigBee等多类型无线连接方式的安全物联网网关设计

随着物联网和云计算技术的飞速发展.物联网终端的数量越来越多&#xff0c;终端的连接方式也更趋多样化&#xff0c;比如 Wi-Fi蓝牙和 ZigBee 等。现有的物联网网关大多仅支持一种或者几种终端的接人方式。无法满足终端异构性的需求。同时&#xff0c;现有的物联网网关与终端设备…...

华清远见嵌入式学习——ARM——作业4

作业要求&#xff1a; 代码运行效果图&#xff1a; 代码&#xff1a; do_irq.c: #include "key_it.h" extern void printf(const char *fmt, ...); unsigned int i 0;//延时函数 void delay(int ms) {int i,j;for(i0;i<ms;i){for(j0;j<2000;j);} }void do_i…...

25. K 个一组翻转链表

题解参考&#xff1a;https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/10416/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/ 设置dummy虚拟头节点&#xff0c;pre为待翻转部分的前驱&#xff08;用于连接&#xff09;&#xff0c;end为待翻转部分中的…...

jQuery的事件-动画-AJAX和插件

一、jQuery事件处理 1.认识事件&#xff08;Event&#xff09; Web页面经常需要和用户之间进行交互&#xff0c;而交互的过程中我们可能想要捕捉这个交互的过程&#xff1a; 比如用户点击了某个按钮、用户在输入框里面输入了某个文本、用户鼠标经过了某个位置&#xff1b;浏…...

【开源】基于JAVA语言的企业项目合同信息系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 合同审批模块2.3 合同签订模块2.4 合同预警模块2.5 数据可视化模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 合同审批表3.2.2 合同签订表3.2.3 合同预警表 四、系统展示五、核心代码5.1 查询合同…...

遗传算法的应用——求解一元函数的极值

遗传算法的应用——求解一元函数的极值 1 基本概念2 预备知识3.1 模拟二进制转化为十进制的方法3.2 轮盘赌选择算法 3 问题4 Matlab代码5 运行效果6 总结 1 基本概念 遗传算法(Genetic Algorithm,GA)是模拟生物在自然环境中遗传和进化过程从而形成的随机全局搜索和优化方法&am…...

Power BI 学习

数据获取 数据清洗 对导入的数据进行数据整理的过程一般称为「数据清洗」&#xff0c;之所以称之为清洗&#xff0c;是因为在数据分析师眼中&#xff0c;杂乱的数据就是脏数据&#xff0c;只有被清洗成干净的数据后才可以进行分析使用。 数据丰富 操作 1.复制列 点击列名选…...

PPT中加入页码

PPT中加入页码 文章目录 简单版本样式更改 简单版本 PPT中插入页码&#xff0c;基础的就是在“插入”选项卡中单机“幻灯片编号”即可 样式更改 然而&#xff0c;就像我们做幻灯片不满足于白底黑字一样&#xff0c;页码也总不能是默认的样式。 比如&#xff0c;在页码下面…...

xxl-job使用笔记

文章目录 xxl-job配置文件新增XxlJobConfig类JobHandler例子xxl-job机制xxl-job-admin配置XxlJob 和 JobHandler(过时了) 其他报错 msg&#xff1a;job handler [demoJobHandler] not found.xxl-job报错 xxl-job registry fail, registryParam:RegistryParam{registryGroup‘EX…...

微短剧,会成为长视频的“救命稻草”吗?

职场社畜秒变霸道总裁&#xff0c;普通女孩穿越成为艳丽皇妃.......这样“狗血”的微短剧&#xff0c;最近不仅在国内各大视频平台上异常火爆&#xff0c;而且还直接火出了国外。 所谓微短剧&#xff0c;就是单集时长从几十秒到十几分钟的剧集&#xff0c;有着相对明确的主题和…...

web架构师编辑器内容-创建业务组件和编辑器基本行为

编辑器主要分为三部分&#xff0c;左侧是组件模板库&#xff0c;中间是画布区域&#xff0c;右侧是面板设置区域。 左侧是预设各种组件模板进行添加 中间是使用交互手段来更新元素的值 右侧是使用表单的方式来更新元素的值。 大致效果&#xff1a; 左侧组件模板库 最初的模板…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...