蓝桥杯-python走迷宫算法
发布日期:2021-06-23 12:16:23 浏览次数:8 分类:技术文章

本文共 2007 字,大约阅读时间需要 6 分钟。

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可 以通行的地方。

迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这个它的上、下、左、右四个方向之一。

 

对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫, 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

 

我们写出一个算法来计算走不同迷宫时的最优路径。

解决方案

首先先清楚我们要迷宫的实质就是一个矩阵,即用(x,y)即可表示迷宫内的任意一点,再用一个字符串w来表示路径。

class Node(object):

     def __init__(self, x, y, w):
         self.x = x
         self.y = y
         self.w = w
 
     def __str__(self):
         return self.w

 

定义好迷宫节点后我们再想一想怎么在迷宫里进行移动,在矩阵里的(x,y)这个点上,x加减1对应着向下和向上移动一格,y加减1就是向右向左移动一格,因此我们用四个函数将这四个移动封装起来,每次移动完成后再w后加上相应的字母;

def up(node):    return Node(node.x - 1, node.y, node.w+"U")    def down(node):    return Node(node.x + 1, node.y, node.w+"D")    def left(node):    return Node(node.x, node.y - 1, node.w+"L")    def right(node):    return Node(node.x, node.y + 1, node.w+"R")
 

 

最后便是算法的主体部分,每次移动的路径用队列储存起来,按照深搜(DFS)的思想进行判断,想了解深搜可以去看作者以前的文章,有详细介绍。

if __name__ == '__main__':

    m, n = map(int, input().split())
    visited = set()
    queue = []
    map_int = [[0] * (n + 1)]
    for i in range(1, m+1):
        map_int.append([0]*(n+1))
        nums = input()
        nums = "0" + nums
        for j in range(0, n+1):
            map_int[i][j] = ord(nums[j]) - 48

    node = Node(1, 1, "")

    queue.append(node)
    while len(queue) != 0:
        moveNode = queue[0]
        queue.pop(0)
        moveStr = str(moveNode.x) + " "+ str(moveNode.y)
        if moveStr not in visited:
            visited.add(moveStr)
            if moveNode.x == m and moveNode.y == n:
                print(len(moveNode.__str__()))
                print(moveNode)
                break
            if moveNode.x < m:
                if map_int[moveNode.x + 1][moveNode.y] == 0:
                    queue.append(down(moveNode))
            if moveNode.y > 1:
                if map_int[moveNode.x][moveNode.y - 1] == 0:
                    queue.append(left(moveNode))
            if moveNode.y < n:
                if map_int[moveNode.x][moveNode.y + 1] == 0:
                    queue.append(right(moveNode))
            if moveNode.x > 1:
                if map_int[moveNode.x - 1][moveNode.y] == 0:
                    queue.append(up(moveNode))

在上述代码中,m,n为矩阵的长和宽,先初始化一个全为0的矩阵,,我们输入完整的矩阵字符串,通过ACCIS编码来转换到矩阵当中去。

解决此类迷宫问题或者类似路径问题,深度优先搜索是关键,要熟练掌握深搜算法,很多类似的路径规划,寻找最优解也会用到很多深搜。

END

主  编   |   张祯悦

责  编   |   刘仕豪

 where2go 团队


   

微信号:算法与编程之美          

长按识别二维码关注我们!

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

转载地址:https://where2go.blog.csdn.net/article/details/104687919 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:服务器遭受攻击的解决办法
下一篇:linux 查询端口占用

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年02月29日 23时46分08秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c语言编程max,C语言编程题及答案.doc 2019-04-21
android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
android增删改查布局,Android之父_增删改查 2019-04-21
vowifi android开关,如何配置VoLTE, ViLTE and VoWifi(IMS config for VoLTE, ViLTE and VoWifi) 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序 2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
由于连接方在一段时间后没有正确答复或连接的主机_新风换气机使用效果不佳,为何?掌握正确使用方法就好了... 2019-04-21
mysql 查询姓王_MySQL查询语句练习题,测试足够用了 2019-04-21
mysql多实例脚本_mysql多实例脚本 2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构 2019-04-21
python获取post请求中的所有参数_Django从POST reques获取请求参数 2019-04-21
mysql加密复制_MySQL主从复制使用SSL加密 2019-04-21
python启动远端 exe_python打包exe开机自动启动的实例(windows) 2019-04-21
java当前路径_java获取当前路径的几种方法 2019-04-21
java web传递参数_Javaweb的八种传值方式 2019-04-21
java gui支持的包有哪两个_Java GUI 2019-04-21