蓝桥杯-python走迷宫算法
问题描述
下图给出了一个迷宫的平面图，其中标记为 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编码来转换到矩阵当中去。
解决此类迷宫问题或者类似路径问题，深度优先搜索是关键，要熟练掌握深搜算法，很多类似的路径规划，寻找最优解也会用到很多深搜。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录