使用遞歸的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，並希望退出可以在更高的水平找到。