python迷宫使用递归

Question

我想使用递归解决迷宫问题。该程序打开一个像这样的文本文件:

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

文件第一行是迷宫的大小(10 20)，第二行是起点(1 1)，第三行是导出(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) 对于这个迷宫是正确的，如果您假设每隔一行和每隔一列都是一条网格线。也就是说，如果 | 和 - 字符代表无限细线，其中偶尔会有中断，很像传统的迷宫图。

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

接下来，您的findpath 函数是困惑的:

首先应该是类的一个方法。它访问内部数据，并包含有关类详细信息的“内部知识”。让它成为一种方法!

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

第三，您有一堆针对各种字符类型的 if 语句。很好，但是请使用

将它们替换为单个 if 语句

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

第四，您等待用“*”标记当前单元格，直到检查结束。但是当你到达导出位置时，你应该在宣布胜利之前标记牢房。我认为，将退出测试下移。

这应该能很好地清理一切。

第五，也是最后，你的递归测试是倒退的。您的代码在到达导出位置时返回 True。当您的代码撞到墙上或试图穿过自己的路径时，您的代码将返回 False。因此，如果代码走死胡同，它会走到尽头，返回false，展开递归几次，一直返回false，直到返回。

因此，如果您曾经看到 True 返回，您就知道代码找到了该路径下的导出。您希望立即返回 true 并且什么都不做。当然不要抹掉路径 - 它通向导出!

另一方面，如果所有可能的方向都没有返回真值，那么您就找到了死胡同——导出不在这个方向。你应该抹掉你的路径，返回False，希望导出能在更高层找到。