我发现这段代码可以解决这样的迷宫：
+-+-+-+-+-+-+-+-+-+-+
| | | | |
S +-+-+-+-+ + +-+ + +
| | | | |
+-+-+-+ +-+ +-+-+-+ +
| | | | |
+ + + + + +-+ +-+-+-+
| | | | | | |
+ + +-+ +-+-+ + + + +
| | | | | | | |
+ +-+ + + + + +-+-+-+
| | | | | |
+ + +-+-+-+ + +-+-+ +
| | | | |
+ +-+-+ +-+-+ +-+-+-+
| | | | | |
+ + + +-+-+-+-+ + +-+
| | | | | | |
+ + + + + + +-+-+-+ +
| | | E
+-+-+-+-+-+-+-+-+-+-+
这是代码：
def read_maze(fname):
mz = []
with open(fname, 'U') as f:
for r in f:
mz.append(list(r.replace('n', '')))
return mz
PATH, START, EXIT, VISITED, SOLUTION = " SE.o"
class Maze():
def __init__(self,maze):
self.maze = maze
self.start_y = [row.count(START) for row in self.maze].index(1)
self.start_x = self.maze[self.start_y].index(START)
def __repr__(self):
return "n".join("".join(row)for row in self.maze)
def solve(self, x=None, y=None):
if x==None:
x, y = self.start_x,self.start_y
if self.maze[y][x] in (PATH,START):
self.maze[y][x] = VISITED
if self.solve(x+1,y) or self.solve(x-1,y) or self.solve(x,y+1) or self.solve(x,y-1):
self.maze[y][x]=SOLUTION
return True
elif self.maze[y][x] == EXIT:
return True
return False
maze = read_maze("maze.txt")
mz = Maze(maze)
print (mz)
print ("-----------------------------")
if mz.solve():
print(mz)
谁能帮我理解递归函数solve()？
首先，函数检查当前位置是在 PATH 还是 START 中，它显然是第一次在 START 中，在我们的例子中是 (x=0;y=2(。因此，代码将其标记为已访问。
我不完全明白的是程序接下来做什么？有一个 if 条件，要检查的第一个选项是 self.solve(x+1,y) - 在这种情况下，我们将向右，这是一个自由位置，它在 PATH 中(所以我们将其标记为 VISITED(，但 (x+1+1，y( 不是，所以我们传递给我们or的第二个值(即(x-1,y)，所以我们再次获得(x+1+(1-1),y) = (x+1,y)， 现在我们转到第三个(x,y+1)所以我们下去等等。
对吗？我有点迷茫。
内联说明
def solve(self, x=None, y=None):
# initializes x, y as start location
# occurs during first call of 'solve', i.e. zeroth recursion
if x==None:
x, y = self.start_x,self.start_y
# equivalent to, if the current (x, y) tile is walk-able
# implicitly ignores visited tiles
if self.maze[y][x] in (PATH,START):
# mark tile (x, y) as visited
self.maze[y][x] = VISITED
# if one of the adjacent tiles from (x, y) leads to a solution
# this is where the recursion occurs, i.e. 'solve' is called using the adjacent tiles
# this will be recursively called until one of the calls return True upon finding the exit
# when one of the calls encounter an exit, then this will create a chain reaction where each call returns True to its caller until the first call returns true
if self.solve(x+1,y) or self.solve(x-1,y) or self.solve(x,y+1) or self.solve(x,y-1):
# mark (x, y) as part of the solution
self.maze[y][x]=SOLUTION
# tells that a solution has been found, value used by caller
return True
# if the (x, y) tile is the exit then a solution has been found
elif self.maze[y][x] == EXIT:
return True
# if non of the if statements return, then by default no solution has been found where tile (x, y) is in the solution path.
return False
迷宫传说
-
<space>可步行瓷砖 -
S开始"磁贴 -
E退出磁贴 -
.访问过的磁贴 -
o作为解决方案路径一部分的磁贴 - 所有其他磁贴均为不可步行磁贴
solve()前的迷宫
+-+-+-+-+-+-+-+-+-+-+
| | | | |
S +-+-+-+-+ + +-+ + +
| | | | |
+-+-+-+ +-+ +-+-+-+ +
| | | | |
+ + + + + +-+ +-+-+-+
| | | | | | |
+ + +-+ +-+-+ + + + +
| | | | | | | |
+ +-+ + + + + +-+-+-+
| | | | | |
+ + +-+-+-+ + +-+-+ +
| | | | |
+ +-+-+ +-+-+ +-+-+-+
| | | | | |
+ + + +-+-+-+-+ + +-+
| | | | | | |
+ + + + + + +-+-+-+ +
| | | E
+-+-+-+-+-+-+-+-+-+-+
solve()后的迷宫
+-+-+-+-+-+-+-+-+-+-+
| |.........|...|...|
oo+-+-+-+-+.+.+-+.+.+
|ooooooo..|.|.....|.|
+-+-+-+o+-+.+-+-+-+.+
|ooo..|o|...|.......|
+o+o+.+o+.+-+.+-+-+-+
|o|o|.|o|.......|...|
+o+o+-+o+-+-+.+.+.+.+
|o|ooo|o|ooo|.|...|.|
+o+-+o+o+o+o+.+-+-+-+
|o|ooo|ooo|o|.......|
+o+o+-+-+-+o+.+-+-+.+
|o|ooooooooo|.|.....|
+o+-+-+ +-+-+.+-+-+-+
|o|ooo| |...| |
+o+o+o+-+-+-+-+.+ +-+
|o|o|o| |ooo....| |
+o+o+o+ +o+o+-+-+-+ +
|ooo|ooooo|oooooooooE
+-+-+-+-+-+-+-+-+-+-+
仅
当代码位于"退出"磁贴或指向"退出"磁贴的路径的一部分上时，solve才会返回True。现在，代码以递归方式潜入迷宫：每次找到"PATH"图块时，它都会将其标记为VISITED并访问所有相邻的图块(下一个递归(或返回"False"的墙图块(无法继续此方向(。这一直持续到最终找到EXIT磁贴，这将返回第一个"True"。这会将递归减少 1 并将 VISITED 标志更改为 SOLUTION ，再次返回True，再次减少递归。现在，这种情况一直持续到代码返回到START磁贴上。
希望这有帮助。