本文共 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]) - 48node = 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!