Python栈--深度优先搜索(迷宫问题)

 给一个二维列表,表示迷宫(0表示给出算法,求通道,1表示围墙)。
 给出算法,求一条走出迷宫的路径。
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

解题思路:

一、整体策略:

        采用回溯法解决迷宫寻路问题。回溯法的核心思想是从起点开始,尝试沿着某条路径前进,当遇到无法前进的情况,就退回到上一个节点,在尝试其他可能得路径,直到找到终点或者确定没有可行的路径为止。

二、先定义dirs列表,用于计算当前节点在上下左右四个方向的相邻坐标,方便在迷宫中移动探索路径。

三、过程:

1.先建一个栈stack,并将起点坐标(x1,y1)压入栈中。

2.当栈不为空时进入循环,取出栈顶元素作为当前节点curNode。

3.检查当前节点是否为终点,如果是,则说明找到一条从起点到终点的路径,此时,遍历栈并输出路径上的节点坐标,然后返回True。

4.如果当前节点不是终点,就遍历dirs中的四个方向函数,通过调用每个函数计算出下一个节点nextNode的坐标。

5.接着判断下一个节点是否是为可通行的通道(即maze[nextNode[0]][nextNode[1]] == 0),如果是,则将该点压入栈中,表示选择该节点在迷宫中的值标记为2,表示已经走过,然后条出本次对方的遍历,继续下一轮循环去探索,并将该节点在迷宫中标记为2表示已经走过,然后跳出本次对方向的遍历,继续下一轮循环去探索新的节点。

6.如果经过四个方向的遍历,都没有找到可通行的节点,就将当前节点在迷宫中的值标记为2(这里其实已经标记过一次了,可优化去掉重复标记),然后将当前节点从栈中弹出,回退到上一个节点,继续尝试其他方向。

四、最终结果判断:

        如果循环结束后栈为空,说明已经尝试了所有可能的路径但都没有找到达终点的路,此时输出“没有路”并返回False。

代码:

代码解析:

1.定义maze和用于计算相邻节点坐标的方向函数列表dirs。

2.maze_path函数接受起点坐标(x1,y1)和终点坐标(x2,y2)作为参数。

3.先创建空栈stack并将起点坐标压入栈中。然后在循环中,不断取出栈顶袁术作为当前节点curNode,并检查是否到达终点,如果到达则输出路径并返回True。

4.这里遍历dirs中的方向函数,通过调佣函数得到下一个节点nextNode的坐标。然后判断下一个节点是否可通行,如果可以就将其压入栈中,并在迷宫中标记为2,表示已走过,然后跳出本次方向遍历,继续探索新节点。

5.如果对四个方向遍历完都没有找到可通行节点,就先在迷宫中再次标记当前尝试的下一个节点为2(可优化去掉这一步,因为前面找到可通行节点时已经标记过了),然后将当前节点从栈中弹出,回退到上一个节点。如果循环结束栈为空,就输出“没有路”并返回False,表示没有找到从起点到终点的路径。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

安卓主板_基于联发科MTK MT8788平台平板电脑方案_安卓核心板开发板定制

联发科MT8788安卓核心板平台介绍: MTK8788设备具有集成的蓝牙、fm、wlan和gps模块,是一个高度集成的基带平台,包括调制解调器和应用处理子系统,启用LTE/LTE-A和C2K智能设备应用程序。该芯片集成了工作在2.0GHz的ARM Cortex-A73、最…

LabVIEW 版本控制

在软件开发中,版本控制系统(VCS) 是管理代码版本变化的核心工具。对于 LabVIEW 用户,虽然图形化编程带来高效开发体验,但由于其特有的二进制 VI 文件格式,传统文本比较工具无法直接用于 LabVIEW 项目。这时…

centos7.9部署oracle19c教程

1.安装前准备 1.1关闭防火墙和selinux systemctl stop firewalld systemctl disable firewalldvi /etc/selinux/config1.2 安装依赖 yum install -y unzip compat-libcap1 compat-libstdc-33 gcc-c ksh libaio-devel libstdc-devel elfutils-libelf-devel fontconfig-devel …

034集——JIG效果实现(橡皮筋效果)(CAD—C#二次开发入门)

可实现效果如下(对象捕捉F3需打开,否则效果不好): public class CircleJig : EntityJig{public static void DraCJig(){PromptPointResult ppr Z.ed.GetPoint("a");if (ppr.Value null) return;Point3d pt ppr.Value…

Softing工业将在纽伦堡SPS 2024上展示Ethernet-APL现场交换机

今年,Softing工业将在纽伦堡SPS贸易展览会上展示aplSwitch Field —— 一款先进的过程自动化解决方案。这款16端口以太网高级物理层(APL)现场交换机的防护等级高达IP30,可提供从应用到现场级别的无缝以太网连接,专为Ex…

鸿蒙UI开发——小图标的使用

1、前 言 鸿蒙SDK中为我们提供了大量的高质量内置图标,图标详见(https://developer.huawei.com/consumer/cn/design/harmonyos-symbol/) 图标资源一览: 除了基本的图标图形外,我们还可以支持图标的多种填充模式(单色、多色、分层…

python3的基本数据类型:Dictionary(字典)的创建

一. 简介 本文开始简单学习一下 python3中的一种基本数据类型:Dictionary(字典)。 字典(dictionary)是Python中另一个非常有用的内置数据类型。 二. python3的基本数据类型:Dictionary(字典&…

2024 年使用 Postman 调用 WebService 接口图文教程

使用 Postman 调用 WebService 接口图文教程

设计字符串类 运算符重载 C++实现 QT环境

问题&#xff1a;设计字符串类&#xff0c; 支持下面的操作 MyString s1; // 默认构造函数 MyString s2("hello"); // 含参构造函数 MyString s3(s1); // 传参构造函数 MyString s4(5, c); // 自定义构造函数 // 运算符重载 ! > < // 运算符重…

链表循环及差集相关算法题|判断循环双链表是否对称|两循环单链表合并成循环链表|使双向循环链表有序|单循环链表改双向循环链表|两链表的差集(C)

判断循环双链表是否对称 设计一个算法用于判断带头节点的循环双链表是否对称 算法思想 让left从左向右扫描&#xff0c;right从右向左扫描&#xff0c;直到它们指向同一个节点&#xff1a;left right 或相邻left->next right&#xff0c;或right->prev left&#x…

基于STM32的智能声控分类垃圾桶(论文+源码)

1系统的功能及方案设计 本次课题为基于STM32的智能声控分类垃圾桶&#xff0c;其系统整体架构如图2.1所示&#xff0c;整个系统包括了stm32f103单片机主控制器&#xff0c;LU-ASR01语音识别模块&#xff0c;WT588语音播报模块&#xff0c;舵机等器件&#xff0c;用户可以通过语…

华大单片机跑历程IO口被写保护怎么解决

一&#xff0c;说明 使用的单片机是HC32F460KETA华大单片机&#xff0c;使用的代码历程是小华单片机历程&#xff0c;具体历程在小华官网都可以找到。   在使用小华历程跑模拟IIC时&#xff0c;SCL时钟是有的&#xff0c;但是IO输入被LOCK了&#xff0c;所以在跑历程进行断点…

网络与通信实验一 网络协议分析

Wireshark的安装 https://www.wireshark.org/&#xff08;下载链接&#xff09; 具体安装步骤参考 安装步骤 点击即可自动跳转 安装后打开 输入ipconfig 选择ipv4网卡存在的设备&#xff08;我的电脑选择WiFi&#xff09; 过滤条件选择 icmp cmd下输入 ping www.baidu.com…

电脑网络丢包怎么排查优化

上网已经成为必不可少的一部分,无论是看视频、玩游戏还是办公,网络的稳定性直接影响到我们的体验。然而有时候会遇到一些问题,比如网页加载慢、视频卡顿、游戏掉线等。这些问题的背后,往往是因为网络丢包。 网络丢包检测工具分享 什么是网络丢包? 网络丢包,简单来说,就是…

从0开始学习Linux——进程管理

往期目录&#xff1a; 从0开始学习Linux——简介&安装 从0开始学习Linux——搭建属于自己的Linux虚拟机 从0开始学习Linux——文本编辑器 从0开始学习Linux——Yum工具 从0开始学习Linux——远程连接工具 从0开始学习Linux——文件目录 从0开始学习Linux——网络配置 从0开…

QT6.5+qt-quick+qml+cmake的Item布局学习

Item 是一个基础元素&#xff0c;它本身不会渲染任何东西&#xff0c;也不会提供一个窗口来显示其内容。Window 是一个可以显示内容的顶级元素&#xff0c;它通常会包含一个或多个子元素来构建用户界面。Item是全部QML可视化对象的根&#xff0c;所有可视化类型都由该类型派生出…

Cameralink转MIPI,Cameralink视频识别分析

CameraLink视频输入转MIPI极简方案&#xff0c;可直接输入到处理芯片中进行视频目标识别与跟踪

【算法】【优选算法】二分查找算法(下)

目录 一、852.⼭脉数组的峰顶索引1.1 二分查找1.2 暴力枚举 二、162.寻找峰值2.1 二分查找2.2 暴力枚举 三、153.寻找旋转排序数组中的最⼩值3.1 二分查找3.2 暴力枚举 四、LCR 173.点名4.1 二分查找4.2 哈希表4.3 暴力枚举4.4 位运算4.5 数学&#xff08;求和&#xff09; 一、…

递归函数学习 part1

一&#xff0c;初始递归&#xff1a;阶乘 1&#xff0c;原理 n的阶乘等于n乘以n-1的阶乘&#xff0c;而0的阶乘等于1. 2&#xff0c;代码展示 #include <iostream> using namespace std;int fact(int); int main() {cout<<fact(5);return 0; }int fact(int n) …

开源 - Ideal库 -获取特殊时间扩展方法(四)

书接上回&#xff0c;我们继续来分享一些关于特殊时间获取的常用扩展方法。 01、获取当前日期所在月的第一个指定星期几 该方法和前面介绍的获取当前日期所在周的第一天&#xff08;周一&#xff09;核心思想是一样的&#xff0c;只是把求周一改成求周几而已&#xff0c;当然其…