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

LeetCode_BFS_中等_1926.迷宫中离入口最近的出口

目录

  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

给你一个 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 一定是空格子。

2.思路

(1)BFS

3.代码实现(Java)

//思路1————BFS
class Solution {public int nearestExit(char[][] maze, int[] entrance) {int m = maze.length;int n = maze[0].length;int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{entrance[0], entrance[1], 0});maze[entrance[0]][entrance[1]] = '+';while (!queue.isEmpty()) {int[] curPos = queue.poll();int curX = curPos[0];int curY = curPos[1];int dis = curPos[2];//朝上下左右四个方向进行遍历for (int[] dir : dirs) {int nx = curX + dir[0];int ny = curY + dir[1];if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {return dis + 1;}maze[nx][ny] = '+';queue.offer(new int[]{nx, ny, dis + 1});}}}return -1;}
}

相关文章:

LeetCode_BFS_中等_1926.迷宫中离入口最近的出口

目录 1.题目2.思路3.代码实现&#xff08;Java&#xff09; 1.题目 给你一个 m x n 的迷宫矩阵 maze &#xff08;下标从 0 开始&#xff09;&#xff0c;矩阵中有空格子&#xff08;用 ‘.’ 表示&#xff09;和墙&#xff08;用 ‘’ 表示&#xff09;。同时给你迷宫的入口 …...

开源Windows12网页版HTML源码

开源Windows12网页版HTML源码&#xff0c;无需安装就能用的Win12网页版来了Windows12概念版&#xff08;PoweredbyPowerPoint&#xff09;后深受启发&#xff0c;于是通过使用HTML、CSS、js等技术做了这样一个模拟板的Windows12系统&#xff0c;并已发布至github进行开源。 这…...

vscode中使用指定路径下的cmake

在 Visual Studio Code 中指定自定义的 CMake 路径&#xff0c;你可以通过以下步骤来实现&#xff1a; 打开你的 CMake 项目所在的文件夹&#xff0c;在 Visual Studio Code 中。 在项目文件夹中&#xff0c;创建一个名为 .vscode 的文件夹&#xff0c;如果它还不存在。 在 .…...

复杂度分析

文章目录 如何分析、统计算法的执行效率和资源消耗&#xff1f;为什么需要复杂度分析&#xff1f;测试结果非常依赖测试环境测试结果受数据规模的影响很大 大O复杂度表示法时间复杂度分析只关注循环次数最多的一段代码加法法则&#xff1a;总复杂度等于量级最大的那段代码的复杂…...

Linux安装jrockit-jdk1.6.0_29-R28.2.0-4.1.0-linux-x64

下载软件&#xff1a;jrockit-jdk1.6.0_29-R28.2.0-4.1.0-linux-x64.bin 执行安装 ./jrockit-jdk1.6.0_29-R28.2.0-4.1.0-linux-x64.bin 安装提示&#xff0c;一路next&#xff0c;注意第二步修改安装的路径&#xff0c;请修改成&#xff1a; <------------------------ O…...

7.2 怎样定义函数

7.2.1 为什么要定义函数 主要内容&#xff1a; 为什么要定义函数 C语言要求所有在程序中用到的函数必须“先定义&#xff0c;后使用”。这是因为在调用一个函数之前&#xff0c;编译系统需要知道这个函数的名字、返回值类型、功能以及参数的个数与类型。如果没有事先定义&…...

Chrome扩展V2到V3的变化

Chrome扩展manifest V3变化、升级迁移指南_chrome_ZK645945-华为云开发者联盟 (csdn.net) 1.background //V2 "background": "background.js"//V3 "background": {"service_worker": "background.js"} 2.executeScript …...

lock、tryLock、lockInterruptibly有什么区别?

lock、tryLock 和 lockInterruptibly 都是用于线程同步的方法,但它们有不同的行为和用途: lock() 方法:lock() 方法是 Java 中 Lock 接口定义的一部分,它用于获取锁并阻塞当前线程,直到锁可用为止。如果锁当前被其他线程占用,lock() 方法会导致当前线程阻塞,直到锁被释放…...

mysql面试题5:索引、主键、唯一索引、联合索引的区别?什么情况下设置了索引但无法使用?并且举例说明

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:说一说索引、主键、唯一索引、联合索引的区别? 索引、主键、唯一索引和联合索引是数据库中常用的索引类型,它们有以下区别: 索引:索引是一种数…...

数据集笔记:纽约花旗共享单车od数据

花旗共享单车公布的其共享单车轨迹数据&#xff0c;包括2013年-2021年曼哈顿、布鲁克林、皇后区和泽西城大约14500辆自行车和950个站点的共享单车轨迹数据 数据地址&#xff1a;Citi Bike System Data | Citi Bike NYC | Citi Bike NYC 性别&#xff08;0未知&#xff1b;1男&…...

为什么 0.1+0.2 不等于 0.3

为什么 0.10.2 不等于 0.3 在 JavaScript 中&#xff0c;0.1 0.2 的结果不等于 0.3&#xff0c;这是因为在 JavaScript 中采用的是双精度浮点数格式&#xff08;64 位&#xff09;&#xff0c;而在这种格式下无法精确表示某些小数&#xff0c;因此在进行计算时会出现精度误差。…...

huggingface_hub v0.17 现已发布

InferenceClient 现在支持所有任务&#xff01;&#x1f4a5;&#xff0c;感谢社区的巨大努力&#xff0c;新添加的任务包括&#xff1a; 对象检测文本分类Token 分类翻译问题回答表格问题回答填充掩码表格分类表格回归文档问题回答视觉问题回答零样本分类 这些方法还支持使用 …...

机器学习——一元线性回归构造直线,并给出损失函数

目 录 Question 问题分析 1.概念补充 2.流程分析 3.注意 具体实现 最终成果 代码 思考&#xff1a; Question 在二维平面有n个点&#xff0c;如何画一条直线&#xff0c;使得所有点到该直线距离之和最短 如果能找到&#xff0c;请给出其损失函数 问题分析 1.概念…...

OpenHarmony自定义组件介绍

一、创建自定义组件 在ArkUI中&#xff0c;UI显示的内容均为组件&#xff0c;由框架直接提供的称为系统组件&#xff0c;由开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑…...

云原生之使用Docker部署PDF多功能工具Stirling-PDF

云原生之使用Docker部署PDF多功能工具Stirling-PDF 一、Stirling-PDF介绍1.1 Stirling-PDF简介1.2 Stirling-PDF功能 二、本次实践规划2.1 本地环境规划2.2 本次实践介绍 三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本 四、下载Stirli…...

B树和B+树的介绍和对比,以及MySQL为何选择B+树

在计算机科学中&#xff0c;B树和B树是常用的数据结构&#xff0c;用于在大规模数据集上进行高效的插入、删除和查找操作。它们在数据库管理系统、文件系统等许多实际应用中发挥着重要作用。本文将深入介绍B树和B树的结构特点、实际应用方面以及它们的优缺点&#xff0c;并最后…...

MD5 绕过第一式:弱比较绕过

文章目录 参考环境MD5韧性脆弱性md5() 隐式类型转换字符串连接数学运算布尔判断相等运算符 科学计数法科学计数法前缀 0E 与 0e PHP8 与 PHP 其他版本下字符串转化为数值的具体规则PHP8数值字符串优化 其他版本更为详细的讲解 字符串与字符串的弱比较字符串与数值的弱比较0e215…...

红黑树是如何实现的?

文章目录 一、红黑树的概念二、红黑树的性质三、红黑树和AVL树对比四、红黑树的插入1. 红黑树的结点定义2. 父亲的颜色3. 叔叔的颜色为红色4. 叔叔不存在5. 叔叔存在且为黑6. 插入的抽象图 五、红黑树的验证1. 检查平衡2. 计算高度与旋转次数3. 验证 六、 红黑树与AVL树的比较 …...

实验室没人导该怎么办

实验室没人教该怎么办 Q: 国内top5高校研一,课题开始老板就给了一个大方向,之后怎么做实验都是自己看文献研究的,终于开始动手做实验,才发现别人根本不想管你,宁愿抱着电脑看剧也不想教你,十分焦虑,该怎么办? A: 按照大多数实验室的惯例,老板一定会指派一个小老板…...

pytest简明教程

1. 简介 pytest是一款基于Python的测试框架。与Python自带的unittest相比&#xff0c;pytes语法更加简洁&#xff0c;断言更加强大&#xff0c;并且在自动测试以及插件生态上比unittest都要更加强大。 1.1. 安装pytest pip install pytest1.2. pytest命名规则 pytest默认会…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...