一道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 

执行结果如下:

题目出处有另一种解题思路,但是我觉得有点烦,自己的这个比较好理解点,实现起来也比较方便。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

您可能感兴趣的文章:

  • Python深度优先算法生成迷宫
  • Python使用Tkinter实现机器人走迷宫
  • Python基于分水岭算法解决走迷宫游戏示例
  • Python使用回溯法子集树模板解决迷宫问题示例
  • Python基于递归算法实现的走迷宫问题
  • 用Python代码来解图片迷宫的方法整理
  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)
(0)

相关推荐

  • Python使用Tkinter实现机器人走迷宫

    这本是课程的一个作业研究搜索算法,当时研究了一下Tkinter,然后写了个很简单的机器人走迷宫的界面,并且使用了各种搜索算法来进行搜索,如下图: 使用A*寻找最优路径: 由于时间关系,不分析了,我自己贴代码吧.希望对一些也要用Tkinter的人有帮助. from Tkinter import * from random import * import time import numpy as np import util class Directions: NORTH = 'North' SOU

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • 用Python代码来解图片迷宫的方法整理

    译注:原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的代码,涉及到用Python对图片的处理以及广度优先(BFS)算法等. 问题by Whymarrh: 当给定上面那样一张JPEG图片,如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫? 我的第一直觉是将这张图按像素逐个读入,并存储在一个包含布尔类型元素的列表或数组中,其中True代表白色像素,False代表非白色像素(或彩色可以被处理成二值图像).但是这种做法存在一个问题,那

  • Python深度优先算法生成迷宫

    本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera

  • 一道python走迷宫算法题

    前几天逛博客时看到了这样一道问题,感觉比较有趣,就自己思考了下方案顺便用python实现了一下.题目如下: 用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径. 如图所示: 先说下我的思路吧: 1.首先用一个列表source存储迷宫图,一个列表route_stack存储路线图,一个列表route_history存储走过的点,起点(0,0),终点(4,4). 2.老鼠在每个点都有上下左右

  • Python走楼梯问题解决方法示例

    本文实例讲述了Python走楼梯问题解决方法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #!python3 ''' 下楼问题.从楼上走到楼下共有h个台阶,每一步有两种走法: 走1个台阶,走2个台阶,问有多少可走的方案.用递归思想和迭代思想编程 ''' ''' 分析:问题可以从最后一次是走1步还是两步,反向考虑 ''' def take_stairs_recursive(n): if n == 1: return 1 elif n == 2: return 2

  • 一道Java集合框架题 多种解题思路

    问题:某班30个学生的学号为20070301-20070330,全部选修了Java程序设计课程,给出所有同学的成绩(可用随机数产生,范围60-100),请编写程序将本班各位同学的成绩按照从低到高排序打印输出. 要求:分别用List.Map.Set来实现,打印的信息包括学号.姓名和成绩. 1.使用List集合来实现 import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; impor

  • 《与孩子一起学编程》python自测题

    测试题一. 1. 程序可以响应的两种事件分别是键盘事件和鼠标事件. 2. 处理事件的代码称为事件处理器 3. Pygame使用KEYDOWN事件来检测按键是否按下. 4. Pos属性会指出事件发生时鼠标所在的位置 5. 要为用户事件得到下一个可用的事件编号,可以使用pygame.NUMEVENTS. 6. 要创建一个定时器,可以使用pygame.time.set_timer(). 7. 要在Pygame窗口中显示文本,可以使用font对象. 8. 使用字体对象有3个步骤: 创建一个字体对象 渲染

  • Python英文文章词频统计(14份剑桥真题词频统计)

    Python剑桥真题词频统计 最好还是要学以致用,自主搜集了19年最近的14份剑桥真题之后,通过Python提供的jieba第三方库,对所有的文章信息进行了词频统计,并选择性地剔除了部分简易词汇,比如数字,普通冠词等,博主较懒,未清楚干净. Python代码如下: import jieba # 以只读方式打开text(即真题库) text = open('text.txt', 'r', encoding = 'utf-8').read() # len(text) #统一为小写 text = te

  • Python利用PaddleOCR制作个搜题小工具

    目录 介绍 安装 安装PaddlePaddle飞桨框架 安装PaddleOCR 代码使用 搜题小工具 安装ADB 截图并保存题目区域图片 OCR识别,获取题目 打开浏览器搜索 完整代码 介绍 PaddleOCR 是一个基于百度飞桨的OCR工具库,包含总模型仅8.6M的超轻量级中文OCR,单模型支持中英文数字组合识别.竖排文本识别.长文本识别.同时支持多种文本检测.文本识别的训练算法. 本教程将介绍PaddleOCR的基本使用方法以及如何使用它开发一个自动搜题的小工具. 项目地址 OR 安装 虽然

  • Python 经典算法100及解析(小结)

    1:找出字符串s="aaabbbccceeefff111144444"中,字符出现次数最多的字符 (1)考虑去重,首先将字符串进行过滤去重,这样在根据这些字符进行循环查询时,将会减少循环次数,提升效率.但是本人写的代码较为臃肿,有更好的希望留言评论 str = 'a1fsfs111bbbcccccvvvvvnnnnboooooosssnb' class Countvalue(): def countvalue(self, str1): ''' 利用set自身的去重功能 :param s

  • Python计算指定日期是今年的第几天(三种方法)

    今天早上和腾讯面试官进行了视频面试,由于音量和网络以及我的垃圾电脑的原因,个人感觉黄了... 最后面试官给了我一道简单的计算题:指定日期是今年的第几年 由于电脑卡到打字都打不动,我勉勉强强写了一点,虽然面试官知道了我的想法也了解我的设备情况,最后没让我写完 但是心里惭愧还是时候补齐了...话不多说回到主题吧 首先是输入的问题,个人认为分别输入年月份是一件很初级的要求,就实现了形如"2020-3-26"的字符串解析的两种方法,代码如下: def cal_date_str_spilt(da

随机推荐