python迷宫万花筒代码_利用广度优先遍历搜索迷宫的python源代码
广度优先遍历简称为DFS，是数据结构中比较常用的一个算法，主要原理是采用队列先进先出的规则，一层一层的访问图的节点。而迷宫问题接近与遍历，但是不同于遍历，主要考虑是采用栈的形式标记路径，并对当前节点和死胡同分别标记为2和3，对死胡同的节点弹出栈，这样循环最终会找到一个路径。当然，存在一个问题就是不一定是最优的路径。
'''
Title:广度优先遍历探索迷宫
Date: 2018-04-18
Author:Jackie
Commont:
1、使用栈stack保存路径
2、采用广度优先遍历，将当前节点(栈的顶点)可用的临近节点全部压栈，并标记为2
3、对于发现死胡同时，将当前节点弹出栈，并标记为3
4、不需要使用队列，因为队列主要实现遍历，而不是最优化
'''
from collections import deque
matrix = [
[0, 1, 0, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]
# dfs function
def dfs_fun(matrix, start, end):
stack = []
stack.append(start)
x, y = start
matrix[x][y] =2
forward = True
while stack:
pos = stack[-1]
if pos == end:
print("Had find last path")
return stack
xPos, yPos = pos
forward = False
if yPos+1 < len(matrix):
if matrix[xPos][yPos+1] ==0:
stack.append((xPos, yPos+1))
matrix[xPos][yPos+1] =2
forward = True
if xPos+1 < len(matrix) :
if matrix[xPos+1][yPos] ==0:
stack.append((xPos+1, yPos))
matrix[xPos+1][yPos] =2
forward = True
if xPos-1 >=0 :
if matrix[xPos-1][yPos] ==0:
stack.append((xPos-1, yPos))
matrix[xPos-1][yPos] =2
forward = True
if yPos-1>=0:
if matrix[xPos][yPos-1] ==0:
stack.append((xPos, yPos-1))
matrix[xPos][yPos-1] =2
forward = True
# bad road
if not forward:
x, y = stack.pop()
matrix[xPos][yPos] = 3
return False
if __name__ == '__main__':
result = dfs_fun(matrix, (0,0), (4,4))
print(result)
相关文章：
联想拯救者Y9000-ubuntu-nvidia-驱动安装
概述 由于联想拯救者Y9000的硬件都比较新，所以在安装ubuntu 的时候会有很多驱动的问题，本文主要讲解安装nvidia驱动的问题，如网卡、触摸板无效的其他问题请在我的其他文章中查找 友情提示 安装完系统之后先插网线装ssh服务， 确…
修改远程桌面端口
修改远程桌面端口需要两个步骤： 1、打开注册表 [HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Terminal Server\Wds\rdpwd\Tds\tcp]，修改右边PortNamber的值，其默认值是3389，修改成所希望的端口即可，例如3…
开发管理 CheckLists(4) -风险管理
本文章主要介绍在项目启动前怎么样分步骤的去识别风险,才去什么方式去识别风险. 有需要做风险识别的朋友可以按照下面的步骤简单的走上一遍,或者可以提高项目的成功率 注意：本文章只是你做风险识别的chekcLists ,上面提到的一些分析方法都只是简单的介绍…
python的深拷贝与浅拷贝
对于list, set, dict来说, 直接赋值. 其实是把内存地址交给变量. 并不是复制⼀份内容. 两个变量的内容其实为一个地址,如果要在复制的同时分配新的地址则需要用到深拷贝和浅拷贝的命令 lst1 ["何炅", "杜海涛","周渝⺠", ["麻花藤", …
safari post 请求接收不到_我是谁？我在哪？我要到哪去？——HTTP请求头
各位小白帽们好又到了新一期的知识点咯在正片开始之前再次提醒一下各位因为联盟管理的需要本周五(12月4日)5点半将会对各位在平台的答题分数进行统计筛选部分排名靠前的童鞋作为核心的正式会员考核压力来了大家是不是有点紧张呢只要积极学习知识积极参与答题向本AI卖萌要flag相…
SharePoint 2013 配置开发环境，需安装VS2012插件
SharePoint 2013已经安装好了，接下来就是配置开发环境，安装VS2012，但是，装好了以后，发现没有SharePoint 2013开发的支持，如下图： 然后，去网上查找资料，VS2012对SharePoin…
联想拯救者Y9000-ubuntu-U盘启动失败解决方法
注意事项 1、U盘要是USB3.0的U盘，否则基本会失败 安装到最后的时候报一个 cd/dvd 设备 low speed的故障 2、bios 设置 硬盘模式 选择 AHCImode 模式， 否则刷机不成功 3、 U盘镜像的烧录方式， 实测windows 下的rufus工具有效
RedHat Enterprise 5.1下OpenLDAP的配置及PAMNSS的配置
服务器端 192.1.0.160 客户机端 192.1.0.221 一、在服务器端配置LDAP服务： 1.下载 openldap-2.4.11.tar.gz和db-4.7.25.tar.gz 2.安装BerkeleyDB #rpm -qa|grep db # tar xvf db-4.7.25.tar.gz # cd db_4.7.25# cd build_unix/# ../dist/configure -prefix/usr/loca…
pwn with glibc heap（堆利用手册）
前言 对一些有趣的堆相关的漏洞的利用做一个记录，如有差错，请见谅。 文中未做说明 均是指 glibc 2.23 相关引用已在文中进行了标注，如有遗漏，请提醒。 简单源码分析 本节只是简单跟读了一下 malloc 和 free 的源码&am…
COCO KeyPoints关键点数据集准备
COCO KeyPoints关键点数据集准备 概述 网上搜了一圈，coco关键点数据集准备的内容比较少，这里写一篇完成的标注流程到数据集准备的文章，以备后忘 标注工具 coco官方标注工具: coco–annotator https://github.com/jsbroks/coco-annotator …
Boost 1.53.0 发布，可移植的C++标准库
Boost 1.53.0 发布了，包含了 5 个新的库，修复了一些安全漏洞以及 Boost.Locale 组件的 bug 。 新增的 5 个库包括： Boost.AtomicBoost.CoroutineBoost.MultiprecisionBoost.Numeric.OdeintBoost.Lockfree完整改进记录说明请看 changelog 下载…
华为云客户端_从技术角度解读华为云手机之于普通用户的可行性
9月1日，华为云宣布，华为首创全球首个ARM芯片的“云手机”正式公测。此消息一出，普通消费市场一片赞美之声，想必大家更多的想法是终于让华为找到了一个应对当前手机困局的解决方案了。据悉，华为云鲲鹏手机早在今年3月就…
c#获取应用程序目录
string str1 Process.GetCurrentProcess().MainModule.FileName;//可获得当前执行的exe的文件名。 string str2Environment.CurrentDirectory;//获取和设置当前目录（即该进程从中启动的目录）的完全限定路径。//备注 按照定义，如果该进程在本…
【BZOJ5311/CF321E】贞鱼/Ciel and Gondolas（动态规划，凸优化，决策单调性）
【BZOJ5311/CF321E】贞鱼/Ciel and Gondolas（动态规划，凸优化，决策单调性） 题面 BZOJCF洛谷 辣鸡BZOJ卡常数！！！！！！ 辣鸡BZOJ卡常数！！&…
python定时任务contrib_django+celery配置(定时任务+循环任务)
下面介绍一下djangocelery的配置做定时任务1.首先介绍一下环境和版本python2.7django 1.8.1celery 3.1.23django-celery 3.1.172.celery的安装sudo pip install celery3.1.23sudo pip install django-celery3.1.173.新建一个项目(1)django-admin startproject django_celery…
CenterNet KeyPoints 关键点训练自己的数据
概述 网上搜了一圈，关于CenterNet 训练关键点数据的资料非常少，而且讲得都很模糊，没法解决实际问题，也未说明细节和要素。在踏坑许久之后，才跑通CenterNet的关键点训练，于是记录一下踏坑历程，以…
Java学习笔记---字符类型
一、字符类型也算是整数类型的一种 字符类型在内存中占有2个字节，可以用来保存英文字母等字符。计算机处理字符类型时，是把这些字符当成不同的整数来看待，因此，严格说来，字符类型也算是整数类型的一种（小写…
我的家庭私有云计划-16
嗯，上午测试S2S的稳定性，改掉几个bug。还挺忙的。这会儿让机器跑测试去，腾出点时间，我们接着聊。 呵呵，昨天哪，已经有朋友批评我了，说我有点贪大求全，这个论坛什么的没必要自己实现&…
“cyl projection cannot cross pole” 解决方法
解决方法： 1、尝试更新NumPy以及相关模块： 在CMD里面执行 conda update –all 遇到提示选择yes/y 更新完毕后看是否可以载入。 发现并不能成功更新，于是采取了下面方法： 2、如果方法一不能解决，那么尝试卸载相关库&…
使用ubuntu（18.04） 作为软路由器连接互联网
使用ubuntu（18.04） 作为软路由器连接互联网 背景: 最近要用ubuntu机器作为中继路由，需要配置一下，但是内网外网网上找了一圈，五花八门的，照着做没有一个靠谱的，遇到的问题也没有任何说明&#…
程序员肿么了？为何总被认为是“屌丝”
没有想到会这么多人，有一点我强调一下，我的标题是被认为，而不是说真是。其实程序员相比其他行业不见得差，只是社会整体认可度不高。（或者说认知） 本文纯属闲时娱乐，请勿当真，请勿较真…
python空值填充_pandas | DataFrame基础运算以及空值填充
今天是pandas数据处理专题的第四篇文章，我们一起来聊聊DataFrame的基本运算。上一篇文章当中我们介绍了DataFrame数据结构当中一些常用的索引的使用方法，比如iloc、loc以及逻辑索引等等。今天的文章我们来看看DataFrame的一些基本运算。数据对齐我们可以…
Python学习之路基础篇--10Python基础，函数进阶
1 命名空间 对于Python 来说命名空间一共有三种 1 内置命名空间 —— Python 解释器 就是Python 解释器一启动就可以使用的名字，储存在内置命名空间中。内置的名字在启动解释器的时候被加载进内存里 2 全局命名空间 —— 我们所命名的，但不是函数中的代码…
C语言中整型浮点型在计算机中的存储
第一次写博客，遣词造句有点菜，算是一次简单梳理，慢慢学习人家的博客风格，随着学习的深入再做修改。 本次学习的是C语言在VS下的编译调试，对于初学者两说，首先说一下如何监控变量，以及监控变量在…
判断交换机性能好坏的九个因素
【文章摘要】把握千兆交换机的主要性能指标是关键，而判断交换机性能的好坏，需要从以下几方面的因素出发... 把握千兆交换机的主要性能指标是关键，而判断交换机性能的好坏，需要从以下几方面的因素出发： 转发技术 …
xgboost回归预测模型_偏最小二乘回归分析法 从预测角度对所建立的回归模型进行比较...
在实际问题中，经常遇到需要研究两组多重相关变量间的相互依赖关系，并研究用一组变量(常称为自变量或预测变量)去预测另一组变量(常称为因变量或响应变量)， 除了最小二乘准则下的经典多元线性回归分析(MLR)，提取自变量组主成分的主…
win7的IE缓存，临时文件，cookies和历史记录
2019独角兽企业重金招聘Python工程师标准>>> vista、win7的缓存以及临时文件、Cookies和历史记录都在以下几个地方： 缓存: %userprofile%\AppData\Local\Microsoft\Windows\Temporary Internet Files Temp: %userprofile%\AppData\Local\Temp Cookies: %…
Sql Server函数全解(四)日期和时间函数
阅读目录 1.获取系统当前日期的函数getDate();2.返回UTC日期的函数UTCDATE()3.获取天数的函数DAY(d)4.获取月份的函数MONTH(d)5.获取年份的函数YEAR(d)6.获取日期中指定部分字符串值的函数DATENAME(dp,d)7.获取日期中指定部分的整数值的函数DATEPART(dp,d)8.计算日期和时间的函…
关于python的比赛_【蓝桥杯】——python集团的比赛技巧,Python,组
【蓝桥杯】—— Python组比赛技巧蓝桥杯是大学生IT学科赛事，由工业和信息化部人才交流中心主办，所以对于大学生还说还是非常值得去参加的，2020年第十一届蓝桥杯新增了大学Python组，不分组别，第一届没有历届的真题&…
杭电 HOJ 1312 Red and Black 解题报告
搜索，bfs。依旧用队列做。边界处懒得处理，全部初始化为-1。当然，0也可以。AC代码如下： #include<iostream> #include<deque> using namespace std;struct Point {int x,y; } x,y;int main() {char str[22];int i,j,n,…