当前位置: 首页 > 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; 左侧组件模板库 最初的模板…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...