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

LeetCode算法题(Go语言实现)_47

news 来源：原创 2025/8/28 14:15:06

题目

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的空格子。entrance 格子不算出口。
请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

一、代码实现

func nearestExit(maze [][]byte, entrance []int) int {m := len(maze)if m == 0 {return -1}n := len(maze[0])if n == 0 {return -1}entranceRow, entranceCol := entrance[0], entrance[1]queue := [][]int{{entranceRow, entranceCol}}maze[entranceRow][entranceCol] = '+' // 标记为已访问directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}steps := 0for len(queue) > 0 {levelSize := len(queue)for i := 0; i < levelSize; i++ {cell := queue[0]queue = queue[1:]row, col := cell[0], cell[1]for _, dir := range directions {newRow := row + dir[0]newCol := col + dir[1]// 检查边界if newRow < 0 || newRow >= m || newCol < 0 || newCol >= n {continue}// 检查是否可走且未访问if maze[newRow][newCol] == '+' {continue}// 检查是否是出口if isExit(newRow, newCol, entranceRow, entranceCol, m, n) {return steps + 1}// 标记为已访问并入队maze[newRow][newCol] = '+'queue = append(queue, []int{newRow, newCol})}}steps++}return -1
}func isExit(r, c, entranceR, entranceC, m, n int) bool {// 位于边界且不是入口return (r == 0 || r == m-1 || c == 0 || c == n-1) && !(r == entranceR && c == entranceC)
}

二、算法分析

1. 核心思路

广度优先搜索（BFS）：从入口出发分层扩展，首次到达边界即最短路径
出口判定：当节点位于迷宫边界且非入口时视为合法出口
状态管理：使用二维数组记录访问状态，避免重复遍历

2. 关键步骤

队列初始化：将入口位置加入队列，步数设为0
分层遍历：每次处理一层节点，检查是否符合出口条件
方向扩展：对合法相邻节点（非墙、未访问）进行入队
终止条件：队列为空时返回-1，表示无可行路径

3. 复杂度

指标	值	说明
时间复杂度	O(mn)	最坏情况遍历所有节点
空间复杂度	O(mn)	维护访问数组和队列的空间消耗

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

入口即出口：入口在边界但不算出口，需寻找其他边界点
全封闭迷宫：所有边界点均为墙，返回-1
螺旋路径：需绕行多层后到达边界出口

2. 扩展应用

动态障碍物：支持实时更新墙的位置后重新计算路径
多出口优化：寻找所有出口中的最近/最远距离
三维迷宫：扩展为三维空间的路径搜索问题

3. 其他语言

from collections import dequedef nearestExit(maze, entrance):m, n = len(maze), len(maze[0])directions = [(-1,0), (1,0), (0,-1), (0,1)]visited = [[False]*n for _ in range(m)]q = deque()# 初始化队列和访问状态ent_r, ent_c = entranceq.append((ent_r, ent_c, 0))visited[ent_r][ent_c] = Truewhile q:r, c, steps = q.popleft()# 判断当前节点是否为出口（边界且非入口）if (r == 0 or r == m-1 or c == 0 or c == n-1) and (r, c) != (ent_r, ent_c):return steps# 遍历四个方向for dr, dc in directions:nr, nc = r+dr, c+dcif 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and maze[nr][nc] == '.':visited[nr][nc] = Trueq.append((nr, nc, steps+1))return -1

五、总结与优化

1. 方法对比

方法	优势	劣势	适用场景
BFS	保证最短路径	空间消耗较大	常规迷宫搜索
DFS	空间效率高	无法保证最短路径	路径存在性验证
A*算法	启发式搜索效率高	需设计启发函数	大型迷宫优化搜索

2. 工程优化

双向BFS：从入口和出口同时搜索，减少搜索空间
压缩存储：使用位运算压缩访问状态数组
并行计算：对多个方向进行并行路径探索

3. 算法扩展

权重迷宫：不同路径消耗不同步数，寻找最小消耗路径
移动模式：支持对角线移动或限定转向次数
动态规划：预处理各点到边界的最短距离

LeetCode算法题(Go语言实现)_47

题目给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘’ 表示）。同时给你迷宫的入口 entrance ，用 entrance [entrancerow, entrancecol…...

编程日记 2025/8/28 14:15:06

树莓派_利用Ubuntu搭建gitlab

树莓派_利用Ubuntu搭建gitlab 一、给树莓派3A搭建基本系统 1、下载系统镜像 https://cdimage.ubuntu.com/ubuntu/releases/18.04/release/ 2、准备系统SD卡二、给树莓派设备联网 1、串口后台登录使用串口登录后台是最便捷的，因为前期网络可能不好直接成功默…...

编程日记 2025/8/17 18:48:35

vi（vim）编辑器和root用户与普通用户之间的转换

vim编辑器是vi编辑器的加强版，以vi为例： vi编辑器： vi编辑器可以编辑文件内容如何进入vi编辑器？ 语法： vi 文件路径如何退出？ 语法： wq：保存退出 w：保存 q&…...

编程日记 2025/8/28 10:21:43

【vscode】vscode链接关联github/gitlab

一、windows下载安装git Git - Downloading Package 二、配置Git的用户名和邮箱 Git Bash运行以下命令来配置Git的用户名和邮箱： git config --global user.name "你的用户名" git config --global user.email "你的邮箱地址" 生成本机秘钥…...

编程日记 2025/8/28 14:13:49

Redis面试问题缓存相关详解

Redis面试问题缓存相关详解一、缓存三兄弟（穿透、击穿、雪崩） 1. 穿透问题描述： 缓存穿透是指查询一个数据库中不存在的数据，由于缓存不会保存这样的数据，每次都会穿透到数据库，导致数据库压力增大。例…...

编程日记 2025/8/28 14:11:30

Web三漏洞学习（其一：文件上传漏洞）

靶场:云曦历年考核题一、文件上传在此之前先准备一个一句话木马将其命名为muma.txt 23年秋期末考来给师兄上个马打开环境以后直接上传muma.txt，出现js弹窗，说明有前端验证提示只能上传.png .jpg 和 .gif文件，那就把muma.txt的后缀…...

编程日记 2025/8/28 14:12:42

冲刺高分！挑战7天一篇nhanes机器学习SCI！DAY1-7

医学生集合啦，继续挑战 7天一篇nhanes机器学习SCI！ Day 1 进展：确定选题、期刊、文献前面挑战了一期NHANES机器学习，大家使用NHANES的发文章的热情，火爆程度远超想象！我在下面的评论区看到大家的学习欲…...

编程日记 2025/8/20 4:51:26

高并发三剑客-本地缓存之王Caffeine-01缓存应用

1 分布式缓存使用及导致的问题 1.1 hotkey典型业务场景常规性hotkey：可以提前评估出hotkey的场景，比如：重要节假日、促销活动等突发性hotkey：没法提前评估，突发性行为，比如：突然新闻、爆炸信息…...

编程日记 2025/8/27 16:46:52

基于Java，SpringBoot，Vue，HTML家政服务预约系统设计

摘要本文聚焦于基于Java、SpringBoot、Vue和HTML技术的家政服务预约系统的设计与实现。该系统旨在为家政服务的供需双方搭建一个便捷、高效的在线交互平台。后端采用Java语言结合SpringBoot框架，充分利用SpringBoot的自动配置和快速开发特性，实现系统业…...

编程日记 2025/8/28 4:15:28

系统架构设计师：系统架构概述知识体系、考点详解、高效记忆要点、练习题并提供答案与解析

一、系统架构概述知识体系、考点详解系统架构概述、定义与作用 1. 系统架构的定义与核心要素系统架构是复杂系统的高层次组织结构，包含硬件/软件组件、交互关系、设计原则及演进策略。其核心要素包括： 构件与模式：现代架构三要素为构件…...

编程日记 2025/8/24 5:49:35

汽配快车道解决chrome backgroud.js(Service Worker) XMLHttpRequest is not defined问题

Chrome 扩展开发：Service Worker 中如何优雅地发送 HTTP 请求在 Chrome 扩展开发中，Service Worker 是一个非常重要的部分，它可以帮助我们实现很多强大的功能。然而，如果你在 Service Worker 中尝试使用 XMLHttpRequest 来发送 …...

编程日记 2025/8/28 14:07:05

VMware Ubuntu挂载Windows机器的共享文件

https://www.dong-blog.fun/post/2029 在VMware Ubuntu中访问Windows共享文件夹：完整指南在使用VMware运行Ubuntu虚拟机时，访问Windows主机上的文件是常见需求。本文将详细介绍如何通过网络共享方式，让Ubuntu虚拟机直接访问Windows主机的文…...

编程日记 2025/8/28 14:13:51

LeNet神经网络

一、LeNet概述 1. 历史地位开创性模型：首个成功应用的卷积神经网络（1998年）应用场景：手写数字识别（MNIST数据集）、银行支票识别提出者：Yann LeCun团队（论文《Gradient-Based Lear…...

编程日记 2025/8/24 2:02:23

Visio绘图工具全面科普：解锁专业图表绘制新境界[特殊字符]

Visio绘图工具全面科普：解锁专业图表绘制新境界🌟 在信息爆炸的时代，清晰、直观地呈现复杂信息变得至关重要。无论是绘制流程图📊、组织结构图👥，还是规划网络拓扑🖧，一款强大的绘图…...

编程日记 2025/8/28 14:12:07

ECharts散点图-散点图3，附视频讲解与代码下载

引言： ECharts散点图是一种常见的数据可视化图表类型，它通过在二维坐标系或其它坐标系中绘制散乱的点来展示数据之间的关系。本文将详细介绍如何使用ECharts库实现一个散点图，包括图表效果预览、视频讲解及代码下载，让你轻松掌握…...

编程日记 2025/8/22 13:57:32

D3路网图技术文档

在本文档中，我们将探讨如何使用 D3.js，结合 SVG（可缩放矢量图形）和 Canvas，来实现高效、交互性强的路网图效果。D3.js 是一个强大的 JavaScript 数据可视化库，可以基于数据驱动文档对象模型（DOM…...

编程日记 2025/8/28 14:12:45

利用 Line Renderer 实现屏幕画画并保存图片 // 当前正在绘制的 LineRendererprivate LineRenderer currentLineRenderer;// 用于保存所有笔触的列表private List<LineRenderer> allLineRenderers new List<LineRenderer>();// 当前笔触顶点计数器private int ve…...

编程日记 2025/8/17 20:58:20

列表、字符串、heapq堆对列算法

1、列表 1.1 访问最后一个元素 list [1, 2, 3, 4, 5, 6] print(list[-1]) # 61.2 访问列表指定范围，例如第1-4个元素 print(list[0, 4]) # [1, 2, 3, 4]1.3 将字符列表以字符串形式输出 list [h, e, l, l, o] ls "".join(list) print(ls) # "…...

编程日记 2025/8/28 1:31:40

实战指南：封装Whisper为FastAPI接口并实现高并发处理

下面给出一个详细的示例，说明如何使用 FastAPI 封装 OpenAI 的 Whisper 模型，提供一个对外的 REST API 接口，并支持一定的并发请求。下面是主要步骤和示例代码。 1. 环境准备 Python 环境： 建议使用 Python 3.8。依赖库&#x…...

编程日记 2025/8/27 18:24:27

Arm系统ubuntu20.04中自带的火狐浏览器打开网页B站视频和百度网盘网页视频，视频无法打开，并且没有声音——（本质上解决）

自己工作过程中有一台Orin nx arm设备，所以希望能够用这台设备看视频学习，发现自带的firefox打开网页版百度网盘和B站的时候无法打开视频，而且用有线耳机发现没有声音，最后换掉浏览器，用Chromium。 1、如果还想继续用…...

编程日记 2025/8/17 20:33:36

Qt 自定义控件

在 Qt 中，自定义控件是通过继承现有的 Qt 控件类（如 QWidget、QPushButton、QLabel 等）并重载相关的事件处理函数或绘制函数来实现的。自定义控件允许你根据需求添加特定的功能或样式。自定义控件的基本步骤 1. 继承 Qt 控件类&#xff1a…...

编程日记 2025/8/25 9:19:12

Java使用WebSocket视频拆帧进度处理与拆帧图片推送，结合Apipost进行调试

<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId></dependency>Configuration public class WebSocketConfig {/*** 启动 WebSocket 服务器*/Beanpublic ServerEndpointE…...

编程日记 2025/8/26 13:03:13

Java项目之基于ssm的QQ村旅游网站的设计（源码+文档）

项目简介 QQ村旅游网站实现了以下功能： 管理员权限操作的功能包括管理景点路线，板块信息，留言板信息，旅游景点信息，酒店信息，对景点留言，景点路线留言以及酒店留言信息等进行回复，…...

编程日记 2025/8/27 14:24:15

《 Reinforcement Learning for Education: Opportunities and Challenges》全文阅读

Reinforcement Learning for Education: Opportunities and Challenges 面向教育的强化学习：机遇与挑战摘要本综述文章源自作者在 Educational Data Mining (EDM) 2021 会议期间组织的 RL4ED 研讨会。我们组织了这一研讨会，作为一项社区建设工作的组…...

编程日记 2025/8/28 14:12:06

Apache Kafka UI ：一款功能丰富且美观的 Kafka 开源管理平台！！

Apache Kafka UI 是一个免费的开源 Web UI，用于监控和管理 Apache Kafka 集群，可方便地查看 Kafka Brokers、Topics、消息、Consumer 等情况，支持多集群管理、性能监控、访问控制等功能。 1 特征多集群管理： 在一个地方监控和管理…...

编程日记 2025/8/26 4:06:55

无参数RCE

无参数RCE（Remote Code Execution，远程代码执行） 是一种通过利用目标系统中的漏洞，在不直接传递用户可控参数的情况下，实现远程执行任意代码的攻击技术。与传统的RCE攻击不同，无参数RCE不依赖外部输入参数…...

编程日记 2025/8/28 13:10:07

设计模式之状态模式：优雅管理对象行为变化

引言状态模式（State Pattern）是一种行为型设计模式，它允许对象在其内部状态改变时改变它的行为，使对象看起来似乎修改了它的类。状态模式将状态转移逻辑和状态相关行为封装在独立的状态类中，完美解决了复杂条件判断问…...

编程日记 2025/8/27 20:15:06

拖动滑块代替验证码，识别机器人的方式，实验原理

拖动滑块验证是一种常见的人机验证技术，用于区分真实用户和自动化程序（如机器人）。其核心原理不仅在于用户是否能将滑块移动到正确位置，还包括对拖动行为的轨迹、速度、加速度等特征的分析。以下是其实现原理及识别机器人的方式&a…...

编程日记 2025/8/28 14:07:07

深度访谈：数据中台的本质不是技术堆砌，而是业务引擎的重构

在数字化转型进入深水区的今天，企业逐渐意识到单纯的技术堆砌无法解决业务核心痛点。数据的割裂、重复建设的烟囱式系统、滞后于业务的分析能力，正迫使企业寻找“系统性解法”。 “未来的竞争，本质是数据响应速度的竞争。当竞争对手还在讨论‘…...

编程日记 2025/8/27 21:43:03

Spark中Maven的用法

在IDEA中去创建项目，并编写java代码来操作集群中的文件 1.IDEA 中创建 Maven 项目步骤一：点击 File -> New -> Project，在弹出的窗口左侧选择 Maven，点击 Next： 步骤二：填写项目的 GroupId、Arti…...

编程日记 2025/8/28 14:10:00

tomcat http 怎么改成 https

步骤 1：生成自签名证书如果你没有可用的 SSL/TLS 证书，可以使用 Java 的 keytool 工具生成一个自签名证书。 bash复制代码 keytool -genkeypair -alias tomcat -keyalg RSA -keystore keystore.jks -keysize 2048 执行此命令后，系统会提…...

编程日记 2025/8/28 14:13:51

Playwright与Selenium详细对比及Playwright快速入门

Playwright 与 Selenium 详细对比及入门指南索引简介本文章旨在帮助测试工程师了解Playwright和Selenium这两个主流的UI自动化测试工具，并快速入门Playwright。文档分为多个部分，本文作为主要索引，提供核心对比和基本概念，而详…...

编程日记 2025/8/28 14:12:46

03 UV

04 Display工具栏_哔哩哔哩_bilibili 讲的很棒 ctrlMMB 移动点 s 打针 ss 批量打针...

编程日记 2025/8/28 14:09:59

hadoop执行sqoop任务找不到jar

sqoop:1.4.7 hadoop:3.4.1 数据:oracel-hdfs 2025-04-15 16:57:00,850 INFO sqoop.Sqoop: Running Sqoop version: 1.4.7 2025-04-15 16:57:00,901 WARN tool.BaseSqoopTool: Setting your password on the command-line is insecure. Consider using -P instead. 2025-04-15 …...

编程日记 2025/8/24 9:09:30

题目