(算法竞赛)使用广度优先搜索(BFS)解决迷宫最短路径问题

在这个充满奇思妙想的世界里,每一次探索都像是打开了一扇通往新世界的大门。今天,我们将踏上一段特别的旅程,去揭开那些隐藏在代码、算法、数学谜题或生活智慧背后的秘密。🎉😊

所以,系好安全带,准备好迎接一场充满欢笑和惊喜的冒险吧!我们的故事,现在正式开始……

题目描述

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。假设你已经得到了一个 n x m 的迷宫的图纸,请你找出从起点到出口的最短路。

输入: 第一行是两个整数 n 和 m (1 ≤ n,m ≤ 100),表示迷宫的行数和列数。 接下来 n 行,每行一个长为 m 的字符串,表示整个迷宫的布局。字符’.‘表示空地,’#'表示墙,'S’表示起点,'T’表示出口。

输出: 输出从起点到出口最少需要走的步数。

样例: 输入:

复制

3 3
S#T
.#.
...

输出:

复制

6

来源: 深搜 递归 广搜

在解决迷宫问题时,尤其是寻找从起点到终点的最短路径时,广度优先搜索(BFS)是一种非常高效且常用的方法。本文将详细解析一个基于 BFS 的 Python 代码,帮助你理解其工作原理和实现细节。

1. 问题背景

迷宫问题是一个经典的路径搜索问题。给定一个二维迷宫,起点为 S,终点为 T,迷宫中包含可通行的格子(用 . 表示)和障碍物(用 # 表示)。目标是找到从起点到终点的最短路径长度。

2. 为什么选择 BFS?

广度优先搜索(BFS)是一种逐层扩展的搜索算法,适用于无权图(迷宫中每个格子的移动代价相同)的最短路径问题。BFS 的核心思想是从起点开始,逐层扩展所有可能的路径,直到找到终点。由于 BFS 按层扩展,最先到达终点的路径一定是最短路径。

3. 代码解析
3.1 输入迷宫数据

Python复制

# 输入网格的行数和列数
n, m = map(int, input().split())
# 输入网格状态
a = [list(input()) for _ in range(n)]
  • 这部分代码首先读取迷宫的行数 n 和列数 m

  • 然后逐行读取迷宫的布局,存储为一个二维字符数组 a。每个格子的值可以是:

    • S:起点。

    • T:终点。

    • .:可通行的格子。

    • #:障碍物。

3.2 定义方向数组

Python复制

# 定义方向数组
dx = [0, 0, 1, -1]  # 行变化(右、左、下、上)
dy = [1, -1, 0, 0]  # 列变化
  • 这两个数组定义了四个可能的移动方向:右、左、下、上。

  • 通过索引 i,可以从 dxdy 中获取对应方向的行和列偏移量。

3.3 找到起点和终点

Python复制

# 找到起点 'S' 和终点 'T' 的位置
start_x, start_y = None, None
end_x, end_y = None, None
for i in range(n):
    for j in range(m):
        if a[i][j] == 'S':
            start_x, start_y = i, j
        elif a[i][j] == 'T':
            end_x, end_y = i, j
  • 遍历迷宫,找到起点 S 和终点 T 的坐标。

  • 如果迷宫中不存在起点或终点,程序将无法正常运行,因此需要确保输入的迷宫包含 ST

3.4 初始化访问标记数组

Python复制

# 初始化访问标记数组
vis = [[False] * m for _ in range(n)]
  • 创建一个与迷宫大小相同的二维数组 vis,用于记录每个格子是否被访问过。

  • 初始时,所有格子标记为未访问(False)。

3.5 BFS 函数实现

Python复制

from collections import deque

def bfs(start_x, start_y):
    queue = deque([(start_x, start_y, 0)])  # 队列中存储 (x, y, 步数)
    vis[start_x][start_y] = True  # 标记起点为已访问

    while queue:
        xx, yy, steps = queue.popleft()  # 当前格子及步数

        # 如果到达终点,返回步数
        if xx == end_x and yy == end_y:
            return steps

        # 遍历四个方向
        for i in range(4):
            x, y = xx + dx[i], yy + dy[i]
            if 0 <= x < n and 0 <= y < m and not vis[x][y] and a[x][y] != '#':
                vis[x][y] = True  # 标记为已访问
                queue.append((x, y, steps + 1))  # 加入队列并步数加1

    return -1  # 如果没有找到路径,返回 -1
  • 队列初始化:使用 deque 创建一个队列,初始时将起点 (start_x, start_y) 和步数 0 加入队列。

  • 逐层扩展:从队列中取出一个格子 (xx, yy),检查是否到达终点。如果是,则返回当前步数。

  • 扩展相邻格子:对于当前格子的四个相邻格子,检查是否在迷宫范围内、未被访问且不是障碍物。如果是,则标记为已访问,并将其加入队列,步数加1。

  • 回溯:如果队列为空且未找到终点,返回 -1,表示无路径。

3.6 调用 BFS 并输出结果

Python复制

# 从起点开始 BFS
if start_x is not None and end_x is not None:
    shortest_path = bfs(start_x, start_y)
    print(shortest_path)
else:
    print("未找到起点或终点")
  • 调用 bfs 函数,从起点开始搜索。

  • 如果找到最短路径,输出路径长度;否则,输出提示信息。

4. 代码运行逻辑
  1. 初始化:读取迷宫数据,找到起点和终点,初始化访问标记数组。

  2. BFS 搜索

    • 从起点开始,逐层扩展所有可能的路径。

    • 使用队列存储当前层的格子及其步数。

    • 每次从队列中取出一个格子,检查是否到达终点。

    • 如果未到达终点,扩展其相邻格子,并将未访问的格子加入队列。

  3. 终止条件

    • 如果到达终点,返回当前步数。

    • 如果队列为空且未找到终点,返回 -1

5. 输入输出示例
输入:

复制

3 3
S#T
.#.
...
输出:
4
6. BFS 的优势
  • 时间复杂度:BFS 的时间复杂度为 O(n×m),适合迷宫规模较大的情况。

  • 空间复杂度:BFS 的空间复杂度为 O(n×m),主要用于存储访问标记数组和队列。

  • 最短路径保证:BFS 按层扩展,最先到达终点的路径一定是最短路径。

7. 总结

本文通过详细解析基于 BFS 的代码,展示了如何高效地解决迷宫最短路径问题。BFS 的逐层扩展特性使其成为解决此类问题的理想选择。通过合理使用队列和访问标记数组,代码能够高效地找到从起点到终点的最短路径,而不会出现超时问题。

队列知识及其在广度优先搜索(BFS)中的应用

队列(Queue)是一种先进先出(First-In-First-Out,FIFO)的数据结构,广泛应用于算法和程序设计中。理解队列的使用,尤其是它在广度优先搜索(BFS)中的关键作用,对于解决路径搜索问题(如迷宫问题)至关重要。


1. 队列的基本概念

队列是一种线性数据结构,其操作类似于现实生活中的排队场景。队列的主要操作包括:

  • 入队(Enqueue):在队列的尾部添加一个元素。

  • 出队(Dequeue):从队列的头部移除一个元素。

  • 查看队头(Peek/Front):查看队列头部的元素,但不移除它。 

队列的特点是先进先出,即最早进入队列的元素会最先被移除。


5. 使用队列的 BFS 与不使用队列的 DFS 的对比

特性BFS(使用队列)DFS(不使用队列)
扩展顺序逐层扩展深度优先
数据结构队列(先进先出)栈(后进先出)
适用场景最短路径问题所有路径问题
时间复杂度O(n×m)O(4n×m)
空间复杂度O(n×m)O(n×m)

 6. 总结

队列是 BFS 的核心数据结构,它通过先进先出的特性确保了 BFS 的逐层扩展。在解决最短路径问题时,BFS 使用队列能够高效地找到从起点到终点的最短路径,而不会像 DFS 那样因深度优先搜索而导致超时。理解队列的使用,对于掌握 BFS 算法至关重要。

希望这篇文章能帮助你更好地理解队列在 BFS 中的应用。如果你对队列或 BFS 仍有疑问,欢迎随时提问!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

支持大功率输出高速频闪的图像处理用光源控制器

机器视觉系统中的光源控制器在确保图像质量、提高系统稳定性、降低能耗以及方便系统扩展和升级等方面发挥着重要作用。它可提供稳定光源&#xff0c;调节参数&#xff0c;另外具有操作便捷性。 下面我们来看Gardasoft的光源控制器&#xff0c;Gardasoft拥有作为图像处理用LED光…

鸿蒙模块概念和应用启动相关类(HAP、HAR、HSP、AbilityStage、UIAbility、WindowStage、window)

目录 鸿蒙模块概念 HAP entry feature har shared 使用场景 HAP、HAR、HSP介绍 HAP、HAR、HSP开发 应用的启动 AbilityStage UIAbility WindowStage Window 拉起应用到显示到前台流程 鸿蒙模块概念 HAP hap包是手机安装的最小单元&#xff0c;1个app包含一个或…

为什么IDEA提示不推荐@Autowired❓️如果使用@Resource呢❓️

前言 在使用 Spring 框架时&#xff0c;依赖注入&#xff08;DI&#xff09;是一个非常重要的概念。通过注解&#xff0c;我们可以方便地将类的实例注入到其他类中&#xff0c;提升开发效率。Autowired又是被大家最为熟知的方式&#xff0c;但很多开发者在使用 IntelliJ IDEA …

【Uniapp-Vue3】uni-icons的安装和使用

一、uni-icon的安装 进入到如下页面中&#xff0c;点击“点击下载&安装”。 uni-icons 图标 | uni-app官网 点击“下载插件并导入HBuilder”&#xff0c;如果没有登录就登陆一下 网页中会打开Hbuilder&#xff0c;进入Hbuilder以后&#xff0c;选择需要使用该插件的项目进…

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(三)

Understanding Diffusion Models: A Unified Perspective&#xff08;三&#xff09; 文章概括 文章概括 引用&#xff1a; article{luo2022understanding,title{Understanding diffusion models: A unified perspective},author{Luo, Calvin},journal{arXiv preprint arXiv:…

群晖docker获取私有化镜像http: server gave HTTP response to HTTPS client].

群晖docker获取私有化镜像提示http: server gave HTTP response to HTTPS clien 问题描述 层级时间用户事件Information2023/07/08 12:47:45cxlogeAdd image from xx.xx.31.240:1923/go-gitea/gitea:1.19.3Error2023/07/08 12:47:48cxlogeFailed to pull image [Get "http…

Charles 4.6.7 浏览器网络调试指南:HTTPS抓包(三)

概述 在现代互联网应用中&#xff0c;网络请求和响应是服务交互的核心。对于开发者和测试人员来说&#xff0c;能够准确捕获并分析这些请求&#xff0c;是保证系统稳定性和性能的关键。Charles作为一个强大的网络调试工具&#xff0c;不仅可以捕获普通的HTTP请求&#xff0c;还…

从spec到iso的koji使用

了解一下Linux发行版流程&#xff1a;:从spec到iso的koji使用 for Fedora 41。 Fedora 41有24235个包&#xff0c;我们选择 minimal 的几十个源码包&#xff0c;百多个rpm包构建。 配3台服务器 40C64G 44C64G 80C128G&#xff0c;有点大材小用&#xff0c;一台就够了 &#xf…

系统思考—复杂问题的根源分析

在企业中&#xff0c;许多问题看似简单&#xff0c;背后却潜藏着复杂的因果关系。传统的思维方式往往只能看到表面&#xff0c;而无法深入挖掘问题的真正根源。我们常常通过“表面解决”来应对眼前的症状&#xff0c;但这往往只是治标不治本。 比如&#xff0c;销量下降时&…

低代码开发:效率革命与市场机遇

一、引言 IT技术推动了全球信息化的浪潮&#xff0c;然而软件开发效率的提升却未能像摩尔定律那样迅速&#xff0c;逐渐成为发展的瓶颈。近年来&#xff0c;低代码领域发展迅猛&#xff0c;不仅诞生了估值超10亿美元的独角兽OutSystems&#xff0c;还吸引了AWS、Google、Micro…

leetcode——相交链表(java)

给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结果后&…

浅谈APP之历史股票通过echarts绘图

浅谈APP之历史股票通过echarts绘图 需求描述 今天我们需要做一个简单的历史股票收盘价格通过echarts进行绘图&#xff0c;效果如下&#xff1a; 业务实现 代码框架 代码框架如下&#xff1a; . 依赖包下载 我们通过网站下载自己需要的涉及的图标&#xff0c;勾选之后进…

【音视频处理】FFmpeg for Windows 安装教程

FFmpeg 是一个强大的多媒体处理工具&#xff0c;可以处理音视频的各种任务&#xff0c;包括格式转换、裁剪、合并等操作&#xff0c;市面上你可以看到的几乎所有的音视频的处理工具内部都离不开FFmpeg的身影。 本文将详细介绍如何在 Windows 系统上安装 FFmpeg。 1. 下载 FFmp…

leetcode刷题记录(八十一)——236. 二叉树的最近公共祖先

&#xff08;一&#xff09;问题描述 236. 二叉树的最近公共祖先 - 力扣&#xff08;LeetCode&#xff09;236. 二叉树的最近公共祖先 - 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科 [https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B…

【28】Word:石油化工设备技术❗

目录 题目 NO1.2 NO3 NO4 题目 NO1.2 F12&#xff1a;另存为将“Word素材.docx”文件另存为“Word. docx”&#xff08;“docx”为文件扩展名&#xff09; 光标来到表格上方→插入→形状→新建画布→单击选中→格式→高度/宽度&#xff08;格式→大小对话框→取消勾选✔锁定…

总线、UART、IIC、SPI

一图流 总线 概念 连接多个部件的信息传输线&#xff0c;是各部件共享的传输介质 类型 片内总线&#xff1a;连接处理器内核和外设的总线&#xff0c;在芯片内部 片外总线&#xff1a;连接芯片和其他芯片或者模块的总线 总线的通信 总线通信的方式 串行通信 数据按位顺序传…

【Postman接口测试】接口用例设计实战—以聚合数据的新闻头条接口为例

在接口测试中&#xff0c;精心设计测试用例是确保接口质量的关键。本文将以聚合数据的新闻头条接口&#xff08;新闻详情查询&#xff09;为例&#xff0c;深入运用多种测试用例设计方法&#xff0c;打造全面且细致的测试用例集。 一、等价类划分法 &#xff08;一&#xff…

Frida使用指南(三)- Frida-Native-Hook

1.Process、Module、Memory基础 1.Process Process 对象代表当前被Hook的进程,能获取进程的信息,枚举模块,枚举范围等 2.Module Module 对象代表一个加载到进程的模块(例如,在 Windows 上的 DLL,或在 Linux/Android 上的 .so 文件), 能查询模块的信息,如模块的基址、名…

ChatGPT结合Excel辅助学术数据分析详细步骤分享!

目录 一.Excel在学术论文中的作用✔ 二.Excel的提示词✔ 三. 编写 Excel 命令 四. 编写宏 五. 执行复杂的任务 六. 将 ChatGPT 变成有用的 Excel 助手 一.Excel在学术论文中的作用✔ Excel作为一种广泛使用的电子表格软件&#xff0c;在学术论文中可以发挥多种重要作用&a…

数字化转型的核心是什么,企业该如何实施?

一、数字化转型的必要性 传统企业在推进业务创新和IT系统建设时&#xff0c;常采用项目式方法&#xff0c;虽经典但易引发“系统烟囱”与“数据孤岛”问题&#xff0c;困扰管理层。 数字化转型是企业战略层面的变革&#xff0c;其核心是利用数字化技术重构业务、流程与组织。…