每天一道leetcode:1926. 迷宫中离入口最近的出口(图论中等广度优先遍历)

今日份题目:

给你一个 m x n 的迷宫矩阵 maze下标从 0 开始),矩阵中有空格子(用 '.' 表示)和墙(用 '+' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作,你可以往 或者 移动一个格子。你不能进入墙所在的格子,你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ,如果不存在这样的路径,请你返回 -1

示例1

输入:maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出:1
解释:总共有 3 个出口,分别位于 (1,0),(0,2) 和 (2,3) 。
一开始,你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以,最近的出口是 (0,2) ,距离为 1 步。

示例2

输入:maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出:2
解释:迷宫中只有 1 个出口,在 (1,2) 处。
(1,0) 不算出口,因为它是入口格子。
初始时,你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以,最近的出口为 (1,2) ,距离为 2 步。

示例3

输入:maze = [[".","+"]], entrance = [0,0]
输出:-1
解释:这个迷宫中没有出口。

提示

  • maze.length == m

  • maze[i].length == n

  • 1 <= m, n <= 100

  • maze[i][j] 要么是 '.' ,要么是 '+'

  • entrance.length == 2

  • 0 <= entrancerow < m

  • 0 <= entrancecol < n

  • entrance 一定是空格子。

题目思路

使用广度优先遍历,和之前的做法一样,用一个队列存放下个可以到达的位置信息,这里我就说一下重点要注意的地方和我踩的坑:

首先,需要一个额外的int型变量存放距离,不能用queue< <int,pair<int,int> > >,要用queue<tuple<int,int,int> >;

其次,将某点加入队列后一定要将这个点设置为墙,我刚开始没有注意到这点,就导致点上下上下一直循环,或者麻烦点用另一个数组标记到达过的点,否则会陷入死循环;

最后,我刚开始想用p.push_back({d+1{nx,ny}}),发现报错,最后学到要用p.emplace(d+1,nx,ny),注意emplace括号里没有大括号。

代码

class Solution 
{
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int n=maze.size();int m=maze[0].size();// 上下左右四个方向int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};queue<tuple<int,int,int> > p;// 入口加入队列p.emplace(0,entrance[0],entrance[1]);// 入口修改为墙,这样就不用额外考虑入口在边界的情况了maze[entrance[0]][entrance[1]]='+';while(!p.empty()){// 获取当前位置的坐标auto [d,x,y]=p.front();p.pop();// 遍历四个方向的格子for(int i=0;i<4;i++){// 获取四周的新坐标int nx=x+dx[i];int ny=y+dy[i];// 新坐标合法且不为墙if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]=='.'){if(nx==0||nx==n-1||ny==0||ny==m-1) //到达边界了{// 新坐标为出口,返回距离作为答案return d+1;}// 修改为墙并加入队列maze[nx][ny]='+'; //注意,不修改为墙会走回来p.emplace(d+1,nx,ny);}}}// 从入口到不了任意出口,返回-1return -1;}
};

提交结果

欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!

更新不易,宝子们点个赞支持下,谢谢!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/92975.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

配置vscode

配置vscode 设置相关 网址&#xff1a;https://code.visualstudio.com/ 搜索不要用百度用这个&#xff1a;cn.bing.com 1.安装中文包 Chinese (Simplified) (简体中文) 2.安装 open in browser 3.安装主题 Atom One Dark Theme 4. 安装图标样式 VSCode Great Icons 5.安装 L…

使用navicat连接postgresql报错问题解决

使用navicat连接postgresql报错问题解决 一、问题现象&#xff1a; 最近使用Navicat来连接postgreSQL数据库&#xff0c;发现连接不上&#xff0c;报错信息如下&#xff1a; 自己百度了一下&#xff0c;发现pgsql 15版本以后&#xff0c;有些系统表的列名改了&#xff0c;pg_…

HTTPS 的加密流程

目录 一、HTTPS是什么&#xff1f; 二、为什么要加密 三、"加密" 是什么 四、HTTPS 的工作过程 1.对称加密 2.非对称加密 3.中间人攻击 4.证书 总结 一、HTTPS是什么&#xff1f; HTTPS (Hyper Text Transfer Protocol Secure) 是基于 HTTP 协议之上的安全协议&…

关于Android Studio Http Proxy设置

对敌人最大的蔑视就是沉默。--鹿丸 我们使用Android Studio 开始构建的时候会有卡顿的情况&#xff0c;甚至死机&#xff0c;也就是所谓的【android studio】构建卡住问题&#xff0c;如果依赖库类都是国内的&#xff0c;检查是否开启了代理 这个地方选择下面的自动代理 国内…

Visual Studio 2019 c++ 自定义注释 ----doxygen

可加入C 也可自定义。 <?xml version"1.0" encoding"utf-8"?> <CodeSnippets xmlns"http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet"><CodeSnippet Format"1.0.0"><Header><Title>注释…

打开vim的语法高亮

在一个Ubuntu中自带的vim版本是8.2.4919&#xff0c;默认就是开始了语法高亮的&#xff0c;打开一个Java文件效果如下&#xff1a; 它不仅仅对Java文件有语法高亮&#xff0c;对很多的文件都有&#xff0c;比如vim的配置文件也有语法高亮&#xff0c;有语法高亮时读起来会容易…

【左神算法刷题班】第17节:在有序二维数组中查找目标值、等于目标字符串的子序列个数

第17节 题目1&#xff1a;在有序二维数组中查找目标值 给定一个每一行有序、每一列也有序&#xff0c;整体可能无序的二维数组 再给定一个数num&#xff0c; 返回二维数组中有没有num这个数 例子 数组如下&#xff0c;找 6 是否存在。 1 3 5 7 2 4 6 13 3 9 14 …

[C++]笔记-函数的栈空间(避免栈空间溢出)

错误1 当数组的内存占用较大时,会引发异常 #include <iostream> using namespace std; int main() {char buff[2000000];cout << (int)buff[sizeof(buff) - 1] << endl; 错误 2 当调用次数较小的时候,栈内存还没有满,可以输出,该地址相减除以1024等于100,就…

CANoe自动化工程的搭建

基于XMLCAPL建立自动化工程 1、导入ini文件2、新建 Test Environment3、报告类型4、代码编写 1、导入ini文件 工程的配置的文件&#xff0c;配置DUT相关信息&#xff0c;具体视工程而编写内容。 2、新建 Test Environment 1、新建XML测试用例环境 2、导入XML测试用例文件 …

奥威BI财务数据分析方案:借BI之利,成就智能财务分析

随着智能技术的发展&#xff0c;各行各业都走上借助智能技术高效运作道路&#xff0c;财务数据分析也不例外。借助BI商业智能技术能够让财务数据分析更高效、便捷、直观立体&#xff0c;也更有助于发挥财务数据分析作为企业经营管理健康晴雨表的作用。随着BI财务数据分析经验的…

一元三次方程求解

一元三次方程求解 题目描述提示输入输出格式输入格式输出格式 输入输出样例输入样例输出样例 算法分析A C 代码 题目描述 有形如&#xff1a; a x 3 b x 2 c x d 0 ax^3bx^2c^xd0 ax3bx2cxd0一元三次方程。给出该方程中各项的系数 ( a a a&#xff0c; b b b&#xff0c;…

解密 AI 客服;在不同硬件设备上运行大型语言模型的可能性

&#x1f989; AI新闻 &#x1f680; 微软必应首席执行官称必应聊天优于OpenAI的GPT-4&#xff0c;但成本更高 摘要&#xff1a;微软必应的首席执行官米哈伊尔・帕拉欣表示&#xff0c;必应聊天表现优于OpenAI的GPT-4&#xff0c;但使用了更高成本的检索增强推理技术。必应聊…

k8s的pv和pvc创建

//NFS使用PV和PVC 1、配置nfs存储 2、定义PV 实现 下图的pv和pvc测试 pv的定义 这里定义5个PV&#xff0c;并且定义挂载的路径以及访问模式&#xff0c;还有PV划分的大小 vim /pv.yamlapiVersion: v1 kind: PersistentVolume metadata:name: pv001 spec:capacity:storage: …

Mac OS minicom 无法设置921600问题

MacOS minicom 无法设置921600问题 介绍过程解决方案参考资料 介绍 minicom是Mac上一款非常好用的串口工具。本文假设你已经安装minicom&#xff0c;并且知道minicom的一般配置和使用方法。这是“MacOS minicom 无法设置921600”的解决问题记录。它在以下环境中设置成功&#…

【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集

【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集 提示:最近开始在【三维重建】方面进行研究,记录相关知识点,分享学习中遇到的问题已经解决的方法。 文章目录 【三维重建】【深度学习】【数据集】基于COLMAP制作自己的NeuS(DTU格式)数据集前言下载…

BDA初级分析——用SQL筛选数据

一、用SQL对数据分组 GROUP BY Group by&#xff0c;按...分组 作用:根据给定字段进行字段的分组&#xff0c;通常和聚合函数配合使用&#xff0c;实现分组的分析 写法:select ...from ...group by 字段名 (也可以是多个字段) GROUP BY的逻辑 SELECT gender,COUNT(user_id) …

数据分析 | 调用Optuna库实现基于TPE的贝叶斯优化 | 以随机森林回归为例

1. Optuna库的优势 对比bayes_opt和hyperoptOptuna不仅可以衔接到PyTorch等深度学习框架上&#xff0c;还可以与sklearn-optimize结合使用&#xff0c;这也是我最喜欢的地方&#xff0c;Optuna因此特性可以被使用于各种各样的优化场景。 2. 导入必要的库及加载数据 用的是sklea…

恒运资本:布林线什么意思?

布林线是一种经过股票价格的标准差核算出涨跌起伏的技能剖析方法。这种剖析方法由约翰布林在1980年左右开发而来&#xff0c;是一种常用的股市剖析东西。本文将从前史、原理、应用等多个视点叙述布林线的含义&#xff0c;以及它对出资者所带来的意义。 一、前史 布林线在1983年…

Kafka 入门到起飞 - 什么是 HW 和 LEO?何时更新HW和LEO呢?

上文我们已经学到&#xff0c; 一个Topic&#xff08;主题&#xff09;会有多个Partition&#xff08;分区&#xff09;为了保证高可用&#xff0c;每个分区有多个Replication&#xff08;副本&#xff09;副本分为Leader 和 Follower 两个角色&#xff0c;Follower 从Leader同…

安防监控视频云存储平台EasyCVRH.265转码功能更新:新增分辨率配置

安防视频集中存储EasyCVR视频监控综合管理平台可以根据不同的场景需求&#xff0c;让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上&#xff0c;视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储…