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

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...