使用递归的python迷宫

Question

我想用递归来解决迷宫问题。程序打开的文本文件是这样一个：

10 20 
1 1 
10 20 
----------------------------------------- 
|  |  | |  | | |  |  | | 
|-+ +-+-+ +-+ + +-+ + + +-+-+ +-+-+ + + | 
|   |  |  | | | | | | | 
| + +-+ + + +-+-+-+ + + + + + +-+ + + + | 
| | | |  |  | |  |  | | | 
| +-+-+-+-+ +-+ +-+-+-+-+ +-+ + +-+-+ +-| 
| | | |  | | |   | | | | 
| + + +-+ +-+-+ + + + +-+ +-+ + + + +-+ | 
|  |  | | |  | | | | | | | 
|-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+ +-+-+ +-| 
| | | |  |  |  | | | | | | 
| +-+-+ +-+-+ +-+ + +-+-+ +-+ +-+ + + + | 
|  |  | | | | | | | |  | 
|-+ +-+ + + +-+ +-+-+ + +-+ + + +-+ +-+ | 
| | | | |  | | | | | | | | | | | | 
|-+ + +-+ + + + + + +-+ + + + + +-+-+ + | 
|  | | | |  |  |    | 
| + + +-+ + +-+-+-+ + +-+ + + +-+-+ +-+ | 
| | |  | |   | | | |  | | 
----------------------------------------- 

该文件的第一行是迷宫（10 20）的大小，第二行的起点（11），以及第三行是出口（10,20）。我想用“*”标记正确的路径。这是我的代码是这样的：

编辑：我改变findpath()函数的一些代码，现在我没有得到任何错误，但迷宫是空的，路径（'*'）不是'绘制'在迷宫中。

class maze():  
    def __init__(self, file): 

     self.maze_list = [] 

     data= file.readlines() 

     size = data.pop(0).split() # size of maze 

     start = data.pop(0).split() # starting row and column; keeps being 0 because the previous not there anymore 
     self.start_i = start[0] # starting row 
     self.start_j = start[1] # starting column 

     exit = data.pop(0).split() # exit row and column 
     self.end_i = exit[0] 
     self.end_j = exit[1] 

     for i in data: 
      self.maze_list.append(list(i[:-1])) # removes \n character off of each list of list 
     print(self.maze_list) # debug 


    def print_maze(self): 

     for i in range(len(self.maze_list)): 
      for j in range(len(self.maze_list[0])): 
       print(self.maze_list[i][j], end='')       
      print() 

def main(): 

    filename = input('Please enter a file name to be processed: ') # prompt user for a file 


    try: 
     file = open(filename, 'r') 
    except:      # if a non-existing file is atempted to open, returns error 
     print("File Does Not Exist") 
     return 

    mazeObject = maze(file) 
    mazeObject.print_maze() # prints maze 

    row = int(mazeObject.start_i) 
    col = int(mazeObject.start_j) 

    findpath(row, col, mazeObject) # finds solution route of maze if any 

def findpath(row, col, mazeObject): 

    if row == mazeObject.end_i and col == mazeObject.end_j: # returns True if it has found the Exit of the maze 
     mazeObject.maze_list[row][col] = ' ' # to delete wrong path 
     return True 

    elif mazeObject.maze_list[row][col] == "|": # returns False if it finds wall 
     return False 

    elif mazeObject.maze_list[row][col] '-': # returns False if it finds a wall 
    return False 

    elif mazeObject.maze_list[row][col] '+': # returns False if it finds a wall 
     return False  

    elif mazeObject.maze_list[row][col] '*': # returns False if the path has been visited 
     return False 

    mazeObject.maze_list[row][col] = '*' # marks the path followed with an * 

    if ((findpath(row + 1, col, mazeObject)) 
     or (findpath(row, col - 1, mazeObject)) 
     or (findpath(row - 1, col, mazeObject)) 
     or (findpath(row, col + 1, mazeObject))): # recursion method 
     mazeObject.maze_list[row][col] = ' ' # to delete wrong path 
     return True 
    return False  

所以现在我的问题是，错误在哪里？我的意思是这个程序只是在没有解决方案的情况下打印迷宫。我想用“*”填充正确的路径。

Answer 1

看着你的代码，我看到了几个错误。您不会正确处理入口和出口行/列对。 （10,20）对于这个迷宫是正确的，如果你认为每隔一行和每一列都是一个网格线。也就是说，如果|和-字符代表无限细线，偶尔会有中断，与传统的迷宫图很像。

为了正确地将您的文件参数转换为数组行/列值，您需要多次/除以二，并处理不可避免的fencepost错误。

接下来，你findpath功能混淆：

首先，它应该是类的方法。它访问内部数据，并包含关于课程细节的“内部知识”。让它成为一种方法！

其次，您的退出条件将用“删除错误路径”的空格替换当前字符。但是如果你找到了出口，那么路径的定义是正确的。不要这样做！

第三，你有一堆if语句，用于各种字符类型。这是好的，但请用

if self.maze_list[row][col] in '|-+*': 
    return False 

四单if语句替换它们，你就等着标记有“*”当前单元格，直到你的检查后。但是，当你到达出口位置时，你应该在宣布胜利之前标记该单元格。我认为，将出口测试向下移动。

这应该很好地清理事情。

第五，最后，你的递归测试是倒退的。当您的代码到达退出位置时，返回True。当您的代码进入墙壁或尝试跨越自己的路径时，您的代码会返回False。因此，如果代码采用死路径，它将达到最后，返回false，将递归展开几次，一直返回false，直到返回。

因此，如果您看到True返回，您知道代码找到了退出该路径。你想立即返回true，并做没有别的。当然，不要擦掉路径 - 它会导致退出！另一方面，如果没有可能的方向返回true，那么你发现了一个死胡同 - 出口不在这个方向。你应该清除你的路径，返回False，并希望退出可以在更高的水平找到。