牛客--迷宫问题

描述

定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围: 2≤n,m≤10 2≤n,m≤10  , 输入的内容只包含 0≤val≤1 0≤val≤1 

输入描述:

输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述:

左上角到右下角的最短路径,格式如样例所示。

输入:
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出:
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

解决:

广度优先搜索BFS

广度优先搜索(Breadth-First Search,简称 BFS)是一种经典的图搜索算法,通常用于解决最短路径问题或搜索问题。BFS 的核心思想是按层级逐步扩展,从起始点开始,先访问离起始点最近的节点,然后逐步向外扩展到更远的节点,直到找到目标节点或遍历完整个图。

BFS 的基本步骤

  1. 初始化

    • 准备一个队列(Queue)来存储待访问的节点。
    • 准备一个访问标记表(通常是一个集合或布尔数组)来记录已访问的节点。
    • 将起始节点加入队列,并标记为已访问。
  2. 迭代搜索

    • 从队列中取出一个节点(称为当前节点)。
    • 处理该节点(例如打印它,或检查是否是目标节点)。
    • 将当前节点的所有未访问邻居加入队列,并标记为已访问。
  3. 结束条件

    • 如果在搜索过程中找到目标节点,到达终点,返回结果。

import sys
from collections import deque

def bfs_maze_solver(n, m, maze):
    # 定义方向数组,上下左右四个方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # 创建队列,存储当前路径和位置
    queue = deque([(0, 0, [(0, 0)])])  # (x, y, path)
    visited = set((0, 0))  # 记录访问过的点

    while queue:
        x, y, path = queue.popleft()

        # 如果到达终点,返回路径
        if (x, y) == (n - 1, m - 1):
            return path
        
        # 遍历四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 检查边界条件和是否能走
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append((nx, ny, path + [(nx, ny)]))
                visited.add((nx, ny))

        
b = []
for line in sys.stdin:
    a = line.split()
    b.append(a)
n,m = [int(i) for i in b[0]]
maze = [[int(j) for j in i] for i in b[1:]]
result = bfs_maze_solver(n, m, maze)
# 输出路径
for step in result:
    print(f"({step[0]},{step[1]})")

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

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

相关文章

Artec Space Spider助力剑桥研究团队解码古代社会合作【沪敖3D】

挑战&#xff1a;考古学家需要一种安全的方法来呈现新出土的陶瓷容器&#xff0c;对比文物形状。 解决方案&#xff1a;Artec Space Spider, Artec Studio 效果&#xff1a;本项目是REVERSEACTION项目的一部分&#xff0c;旨在研究无国家社会中复杂的古代技术。研究团队在考古地…

云原生服务网格Istio实战

基础介绍 1、Istio的定义 Istio 是一个开源服务网格&#xff0c;它透明地分层到现有的分布式应用程序上。 Istio 强大的特性提供了一种统一和更有效的方式来保护、连接和监视服务。 Istio 是实现负载平衡、服务到服务身份验证和监视的路径——只需要很少或不需要更改服务代码…

《Cocos Creator游戏实战》非固定摇杆实现原理

为什么要使用非固定摇杆 许多同学在开发摇杆功能时&#xff0c;会将摇杆固定在屏幕左下某一位置&#xff0c;不会让其随着大拇指触摸点改变&#xff0c;而且玩家只有按在了摇杆上才能移动人物&#xff08;触摸监听事件在摇杆精灵上)。然而&#xff0c;不同玩家的大拇指长度不同…

智能座舱进阶-应用框架层-Jetpack主要组件

Jetpack的分类 1. DataBinding&#xff1a;以声明方式将可观察数据绑定到界面元素&#xff0c;通常和ViewModel配合使用。 2. Lifecycle&#xff1a;用于管理Activity和Fragment的生命周期&#xff0c;可帮助开发者生成更易于维护的轻量级代码。 3. LiveData: 在底层数据库更…

登山第十六梯:深度恢复——解决机器人近视问题

文章目录 一 摘要 二 资源 三 内容 一 摘要 深度感知是基于 3D 视觉的机器人技术的一个重要问题。然而&#xff0c;现实世界的主动立体或 ToF 深度相机经常会产生嘈杂且深度不完整&#xff0c;从而成为机器人性能的瓶颈。在这项工作中&#xff0c;提出了 一个基于学习的立体…

【Jenkins】持久化

文章目录 持续集成CI持续部署CD部署部署到linux服务器 持续集成好处&#xff1a; 持续集成CI 持续集成&#xff08;Continuous integration&#xff0c;简称CI&#xff09;指的是频繁地&#xff08;一天多次&#xff09;将代码集成到主干。 持续集成的目的就是让产品可以快速…

小红书飞书素材库 | AI改写 | 无水印下载 | 多维表格 | 采集同步 | 影刀RPA

小红书飞书素材库 | AI改写 | 无水印下载 | 多维表格 | 采集同步 | 影刀RPA 模板准备 进入【小红书】素材采集库_荷逸模板&#xff0c;点击使用模板 创建文档应用 在开发者后台 - 飞书开放平台创建 企业自建应用 (需要账号有相应的权限, 如果没有权限向管理员申请) 获取 Ap…

layui动态拼接生成下拉框验证必填项失效问题

利用 jQuery 动态拼接下拉框时&#xff0c;lay-verify"required" 失效了&#xff0c;有以下几种原因。 1. <form></form>标签 加入 layui 类&#xff0c;class"layui-form" 。提交按钮上加自动提交&#xff0c;lay-submit ""; 。需…

合合信息:探索视觉内容安全新前沿

2024年12月13日-15日&#xff0c;中国图象图形学学会在杭州召开。大会期间&#xff0c;来自合合信息的图像算法研发总监郭丰俊进行了主题为“视觉内容安全技术的前沿进展与应用”的演讲&#xff0c;介绍了视觉内容安全问题&#xff0c;并总结了现今的技术发展&#xff0c;对我很…

阿里云cdn稳定吗?

阿里云CDN&#xff08;内容分发网络&#xff09;是阿里云提供的一项全球加速服务&#xff0c;它的稳定性通常被认为是非常高的&#xff0c;尤其在国内市场。九河云给大家总结了阿里云CDN的稳定性情况&#xff1a; 1. 全球节点覆盖广泛 阿里云CDN在全球范围内拥有数百个加速节…

本地部署webrtc应用怎么把http协议改成https协议?

环境&#xff1a; WSL2 Ubuntu22.04 webrtc视频聊天应用 问题描述&#xff1a; 本地部署webrtc应用怎么把http协议改成https协议&#xff1f; http协议在安卓手机浏览器上用不了麦克风本&#xff0c;来地应用webrtc 本来是http协议&#xff0c;在安卓手机上浏览器不支持使…

Qt creator ,语言家功能缺失解决方法

1、找到工具->外部->配置 2、添加目录&#xff0c;双击命名语言家 3、在语言家目录下&#xff0c;添加工具 双击重命名lupdate&#xff0c;即更新翻译 %{CurrentDocument:Project:QT_INSTALL_BINS}\lupdate%{CurrentDocument:Project:FilePath}%{CurrentDocument:Projec…

用于UISystem的工具集

简介&#xff1a;上篇文章用于管理Unity中UGUI的工具系统UISystem-CSDN博客讲了UISystem&#xff0c;为了更加方便使用&#xff0c;我给他写了一个编辑器工具&#xff0c;下面展示代码和使用说明&#xff0c;具体详情不难看一下就看懂了。 一、代码部分 using QFramework; us…

onlyoffice连接器 二次开发 合同等制式模板化技术开发方案【三】

一、期望效果 目前曹瑞版本onlyoffice已经实现&#xff1a;书签模式 和 控件模式&#xff0c;用以支持该方案。 【图1】字段绑定 【图2】模板发起 【图3】接入表单 思路讲解&#xff1a; 业务系统开发中通常希望能够通过绑定form字段给word&#xff0c;从而达到双向同步效果&am…

WPF+MVVM案例实战与特效(四十五)- 打造优雅交互:ListBox 的高级定制与行为触发(侧边菜单交互面板)

文章目录 1、引言2、案例效果3、案例实现1、依赖安装2、文件创建3、代码实现1、依赖引用与上下文2、个性化视觉效果:自定义 ItemContainerStyle3、页面样式与布局完整代码4、ViewModel 逻辑实现5、子界面代码:3、实现效果4、源代码获取5、总结1、引言 在WPF应用程序开发中,…

【优选算法】复写零

链接&#xff1a;1089. 复写零 - 力扣&#xff08;LeetCode&#xff09; 算法原理&#xff1a; 解法&#xff1a;双指针算法 根据“异地”操作&#xff0c;然后优化成双指针下的“就地”操作 1.先找到最后一个“复写”的数 1.先判断 cur 位置的值 2.决定 dest 向后移动一步或…

moviepy将图片序列制作成视频并加载字幕 - python 实现

DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 需要更多数据资源和技术解决方案&#xff0c;知识星球&#xff1a; “DataBall - X 数据球(free)” -------------------------------------------------------------…

ubuntu20.04安装imwheel实现鼠标滚轮调速

ubuntu20.04安装imwheel实现鼠标滚轮调速 Ubuntu 系统自带的设置中仅具备调节鼠标速度的功能&#xff0c;而无调节鼠标滚轮速度的功能。其默认的鼠标滚轮速度较为缓慢&#xff0c;在查看文档时影响尚可接受&#xff0c;但在快速浏览网页时&#xff0c;滚轮速度过慢会给用户带来…

ubuntu开机进入initramfs状态

虚拟机卡死成功起后进入了initramfs状态&#xff0c;可能是跟文件系统有问题或者检索不到根文件系统&#xff0c;或者是配置错误&#xff0c;系统磁盘等硬件问题导致 开机后进入如下图的界面&#xff0c; 文中有一条提示 要手动fsck 命令修复 /dev/sda1 命令如下 fsck /de…

STL格式转换为OBJ格式

STL格式与OBJ格式简介 STL格式 STL&#xff08;Stereo Lithography&#xff09;文件是一种用于3D打印和计算机辅助制造&#xff08;CAM&#xff09;的文件格式。它最初由3D Systems公司开发&#xff0c;主要用于立体光刻技术。STL文件通常分为二进制和ASCII两种格式&#xff…