在python解决迷宫

Question

您好，我发现这个代码来解决这样的迷宫：

+-+-+-+-+-+-+-+-+-+-+ 
| |   | | | 
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) 

谁能帮助我了解递归函数求解（） ？

首先检查当前位置是否在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），所以我们下去等

难道是正确的，我迷路了一下。

Answer 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出口瓷砖
• .solve()

  +-+-+-+-+-+-+-+-+-+-+ 
  | |   | | | 
  S +-+-+-+-+ + +-+ + + 
  |   | |  | | 
  +-+-+-+ +-+ +-+-+-+ + 
  |  | | |  | 
  + + + + + +-+ +-+-+-+ 
  | | | | |  | | 
  + + +-+ +-+-+ + + + + 
  | | | | | | | | 
  + +-+ + + + + +-+-+-+ 
  | | | | |  | 
  + + +-+-+-+ + +-+-+ + 
  | |   | |  | 
  + +-+-+ +-+-+ +-+-+-+ 
  | | |  | | | 
  + + + +-+-+-+-+ + +-+ 
  | | | | |  | | 
  + + + + + + +-+-+-+ + 
  | |  |   E 
  +-+-+-+-+-+-+-+-+-+-+ 
  

  迷宫前后走访瓷砖

• o瓦片是解决路径的一部分
• 所有其他瓷砖都是非步行能够瓷砖

迷宫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 
+-+-+-+-+-+-+-+-+-+-+ 

Answer 2

solve回报True只有当代码位于Exit瓦片或通往Exit瓦片的路径的一部分时，代码才会递归地进入迷宫：每次找到'PATH'瓦片时，它会将其标记为VISITED并访问所有相邻的瓦片（下一次递归）或者它返回的墙砖ns'False'（不能继续这个方向）。这一直持续到EXIT瓦片终于找到，它返回第一个'真'。这将递归减1，并将VISITED标志更改为SOLUTION，再次返回True，再次递减递归。现在继续，直到代码返回到START平铺。

希望这会有所帮助。