下图给出了一个迷宫的平面图,其中标记为 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编码来转换到矩阵当中去。
解决此类迷宫问题或者类似路径问题,深度优先搜索是关键,要熟练掌握深搜算法,很多类似的路径规划,寻找最优解也会用到很多深搜。