在Python中找到迷宫的出口
这个问题是要找到从迷宫中出去的路。我在这段代码里找不到错误。迷宫的编码方式是这样的：1代表坑（或者墙，具体看情况），0代表通道，2和3代表已经走过的地方。方向上，S是南（向下），E是东（向左），N是北（向上），W是西（向左）。lepes()是主要的函数，它负责递归移动。x和y分别是当前移动的横坐标和纵坐标。顺便说一下，迷宫的大小是12 x 12，周围都是坑（墙，默认是1）。真正的活动区域是10 x 10。所有走过的路径都会存储在列表s中，最开始是s = []。变量lab用来存储迷宫的布局。
我只是想找到走出迷宫的路。我用Python写了这段代码：
def lepes(x, y, lab, s):
if x != 10 and y !=10:
# step forward...
lab[x][y] = 3
# can I move down?
if x < 11 and lab[x+1][y] == 0 :
s.append("S")
lepes(x+1, y, lab, s)
# can I move right?
if y < 11 and lab[x][y+1] == 0:
s.append("E")
lepes(x, y+1, lab, s)
# can I move up?
if x > 0 and lab[x-1][y] == 0:
s.append("N")
lepes(x-1, y, lab, s)
# can I move left?
if y > 0 and lab[x][y-1] == 0:
s.append("W")
lepes(x, y-1, lab, s)
# step back...
# mark as visited
#lab[x][y] = 2
s.append("")
#s.pop()
else:
# The goal is reached, and last step forward...
lab[x][y] = 3
return
# last step back
lab[x][y] = 2
为了找到出迷宫的路，我尝试从起点(1, 1)调用函数lepes(1, 1, lab, s)。我需要到达坐标(10, 10)的地方：
这是lab的初始值：
lab = [[1,1,1,1,1,1,1,1,1,1,1,1],[1,0,0,0,0,0,0,0,0,0,0,1],[1,0,1,1,1,1,1,1,0,1,1,1],[1,0,1,0,0,0,0,0,0,0,0,1],[1,0,1,0,1,1,1,1,1,1,0,1],[1,0,1,0,1,0,0,0,0,0,0,1],[1,0,0,0,1,1,0,1,1,1,0,1],[1,0,1,0,0,0,0,1,0,1,1,1],[1,0,1,1,0,1,0,0,0,0,0,1],[1,0,1,0,0,1,1,1,1,1,0,1],[1,0,0,0,1,1,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1,1,1]]
最终的解决方案形式是："".join(s)，我得到了这个结果：
s = "SSSSSSSSSEESESSWSEESEEEENNNEEEEWNNNEEEEEEENNEEWWWWWW"
我应该得到类似这样的结果：
s = "SSSSSEENNNEEEEEEESSWWWWSSSEEEESS"
黄色部分是起点，绿色部分是目标。
2 个回答
如果你想找到最短的路径，我建议你可以这样做：
把你的迷宫转换成一个加权图，具体步骤如下：
把所有可以通行的方格当作图中的点。
把所有相邻的可以通行的方格之间的连接关系当作图中的边。
每条边的权重都设为1。
然后就可以让Dijkstra算法或者A*算法来帮你解决这个问题了。
我找到的最短路径是“SSSSSEESEEESEEEESS”。
下面是我用来找到这个路径的简单代码：
#! /usr/bin/python3
lab = [[1,1,1,1,1,1,1,1,1,1,1,1],[1,0,0,0,0,0,0,0,0,0,0,1],[1,0,1,1,1,1,1,1,0,1,1,1],[1,0,1,0,0,0,0,0,0,0,0,1],[1,0,1,0,1,1,1,1,1,1,0,1],[1,0,1,0,1,0,0,0,0,0,0,1],[1,0,0,0,1,1,0,1,1,1,0,1],[1,0,1,0,0,0,0,1,0,1,1,1],[1,0,1,1,0,1,0,0,0,0,0,1],[1,0,1,0,0,1,1,1,1,1,0,1],[1,0,0,0,1,1,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1,1,1]]
class Node:
def __init__ (self, x, y):
self.x = x
self.y = y
self.neighbours = [ (x + xoff, y + yoff) for xoff, yoff in
( (1, 0), (0, 1), (0, -1), (-1, 0) )
if not lab [y + yoff] [x + xoff] ]
self.distance = ...
self.path = ...
self.visited = False
def __repr__ (self):
return '{}: ({})'.format ( (self.x, self.y), self.neighbours)
nodes = {}
for y in range (12):
for x in range (12):
if lab [y] [x]: continue
nodes [x, y] = Node (x, y)
current = nodes [1, 1]
current.distance = 0
current.path = []
unvisited = set (nodes.keys () )
while True:
dist = current.distance + 1
for nx, ny in current.neighbours:
if (nx, ny) not in unvisited: continue
neighbour = nodes [nx, ny]
if neighbour.distance is ... or neighbour.distance > dist:
neighbour.distance = dist
neighbour.path = current.path + [ (current.x, current.y) ]
current.visited = True
unvisited.remove ( (current.x, current.y) )
if not unvisited: break
current = sorted ( [node for node in nodes.values ()
if not node.visited and node.distance is not ...],
key = lambda node: node.distance) [0]
print (nodes [10, 10].path)
path = nodes [10, 10].path + [ (10, 10) ]
for (ax, ay), (bx, by) in zip (path, path [1:] ):
if ax == bx and ay > by: print ('N', end = '')
if ax == bx and ay < by: print ('S', end = '')
if ay == by and ax > bx: print ('W', end = '')
if ay == by and ax < bx: print ('E', end = '')
print ()
结果是：
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (3, 7), (4, 7), (5, 7), (6, 7), (6, 8), (7, 8), (8, 8), (9, 8), (10, 8), (10, 9)]
SSSSSEESEEESEEEESS
或者，如果你从右上角开始，结果是：
[(10, 1), (9, 1), (8, 1), (8, 2), (8, 3), (9, 3), (10, 3), (10, 4), (10, 5), (9, 5), (8, 5), (7, 5), (6, 5), (6, 6), (6, 7), (6, 8), (7, 8), (8, 8), (9, 8), (10, 8), (10, 9)]
WWSSEESSWWWWSSSEEEESS
你的if语句并不是互斥的。在每个if语句里，你都在递归调用这个函数，但当这个递归调用返回后，程序会继续执行，可能会进入同一个位置的其他代码块。
你可以考虑把它们改成elif，但我个人觉得递归在这里可能不是最好的解决办法（除非你是想用函数式编程的风格）：更好的方法是在最上面用一个while循环，然后在每个if的分支里更新x和y。