一道python走迷宫算法题
作者:sinly100 发布时间:2022-08-11 19:14:25
标签:python,迷宫,算法
前几天逛博客时看到了这样一道问题,感觉比较有趣,就自己思考了下方案顺便用python实现了一下。题目如下:
用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径。
如图所示:
先说下我的思路吧:
1、首先用一个列表source存储迷宫图,一个列表route_stack存储路线图,一个列表route_history存储走过的点,起点(0,0),终点(4,4)。
2、老鼠在每个点都有上下左右四种方案可选,需要定义这些方案的执行方法。
3、最后做一个循环,如果当前点不是(4,4)的话就依次执行上下左右四种方法,但是有些限制,比如尝试走过的点不会再尝试走,(0,x)点无法再执行向上的方法等等。
贴一下代码:
# _*_ coding:utf-8 _*_
route_stack = [[0,0]]
route_history = [[0,0]]
source=[[0,0,1,0,1],[1,0,0,0,1],[0,0,1,1,0],[0,1,0,0,0],[0,0,0,1,0]]
def up(location):
#横坐标为0,无法再向上走
if location[1] == 0:
return False
else:
new_location = [location[0],location[1]-1]
#已经尝试过的点不会尝试第二次
if new_location in route_history:
return False
#碰到墙不走
elif source[new_location[0]][new_location[1]] == 1:
return False
else:
route_stack.append(new_location)
route_history.append(new_location)
return True
def down(location):
if location[1] == 4:
return False
else:
new_location = [location[0],location[1]+1]
if new_location in route_history:
return False
elif source[new_location[0]][new_location[1]] == 1:
return False
else:
route_stack.append(new_location)
route_history.append(new_location)
return True
def left(location):
if location[0] == 0:
return False
else:
new_location = [location[0]-1,location[1]]
if new_location in route_history:
return False
elif source[new_location[0]][new_location[1]] == 1:
return False
else:
route_stack.append(new_location)
route_history.append(new_location)
return True
def right(location):
if location[0] == 4:
return False
else:
new_location = [location[0]+1,location[1]]
if new_location in route_history:
return False
elif source[new_location[0]][new_location[1]] == 1:
return False
else:
route_stack.append(new_location)
route_history.append(new_location)
return True
lo = [0,0]
while route_stack[-1] != [4,4]:
if up(lo):
lo = route_stack[-1]
continue
if down(lo):
lo = route_stack[-1]
continue
if left(lo):
lo = route_stack[-1]
continue
if right(lo):
lo = route_stack[-1]
continue
route_stack.pop()
lo = route_stack[-1]
print route_stack
执行结果如下:
题目出处有另一种解题思路,但是我觉得有点烦,自己的这个比较好理解点,实现起来也比较方便。
来源:http://blog.csdn.net/sinly100/article/details/72832805
0
投稿
猜你喜欢
- GMSSL模块介绍GmSSL是一个开源的加密包的python实现,支持SM2/SM3/SM4等国密(国家商用密码)算法、项目采用对商业应用友
- QComboBox 是一个允许用户从列表选项中选择一项的控件。#!/usr/bin/python3# -*- coding: utf-8 -
- 首先,在数据库中创建一个表,用于存放图片:CREATE TABLE Images(Id INT PRIMARY KEY AUTO_INCRE
- 错误号 错误信息5 &n
- 可能许多同学对SQL Server的备份和还原有一些了解,也可能经常使用备份和还原功能,我相信除DBA之外我们大部分开发员队伍对备份和还原只
- 1.漏洞介绍在XHTML 1.0标准下,使用特殊构造的CSS样式,在Internet Explorer 7.0
- 不管是用import还是用from mmmm import *的方式导入模块,当程序运行之后,回头在看那个存储着mmmm.py文件的目录中,
- 今天在工作中遇到了一个问题,需要按时间查询,可是查询出来的结果显示的不正确。举个例子来说,要查找出2007-10-12至2007-10-31
- 本文将介绍PHP中单引号和双引号的区别。PHP中单引号和双引号简介在 PHP 中,我们使用引号来指定值是字符串文字。有两种不同类型的报价。它
- 计算机视觉方面朋友都需要跟图像打交道,在pytorch中图像与我们平时在matlab中见到的图像数据格式有所不同。matlab中我们通常使用
- 新建一个项目 app02在 app02/ 下创建 urls.py:from django.conf.urls import urlfrom
- 又一个js加密工具:js混淆,完整源代码如下,有点长呵呵:<HTML><HEAD><TITLE>Cunf
- 本文作为属性篇的最后一篇文章, 将讲述HTML和CSS的关键—盒子模型(Box model). 理解Box model的关键便是margin
- 散点图散点图是指在 回归分析中,数据点在直角坐标系平面上的 分布图,散点图表示因变量随 自变量而 变
- 很多朋友使用Dreamweaver一段时间后,开始热衷于寻找各式各样的插件,追求各种各样的特效,而对于Dreamweaver中的基本功能反而
- 什么是树表查询?借助具有特殊性质的树数据结构进行关键字查找。本文所涉及到的特殊结构性质的树包括:二叉排序树。 平衡二叉树。使用上述树结构存储
- 爬虫数据保存到mongoDB的方法:import pymongo# 首先需要注意,mongodb数据库存储的类型是以键值
- 本文实例讲述了php使用Cookie实现和用户会话的方法。分享给大家供大家参考。具体分析如下:PHP 包含了很多的函数,可以用来管理和记录用
- 1. 停应用层的各种程序。 2. 停oralce的监听进程: $lsnrctl stop 3. 在独占的系统用户下,备份控制文件: SQL&
- 思想:4个数字的排列,加上3个运算符的排列,使用后缀表达式的表现如下:情形一:1,2,3,4,+,-,* => 24*24*4情形二: