maze - 通过迷宫找到路径

Question

我想在迷宫中从起点到终点找到不同的可能路径我已经编写了代码，但它只给了我迷宫中的一些路径...我想要所有路径请给出一些建议

Answer 1

使用生成器的解决方案：

grid = [[0,0,0,0],
        [0,1,0,0],
        [0,0,1,0],
        [0,0,0,0]]

def search(sr, sc, er, ec, path):

    if sr < 0 or sc < 0 or sr >= len(grid) or sc >= len(grid[0]):
        return
    if (sr, sc) in path or grid[sr][sc] == 1:
        return

    path.append((sr, sc))
    if (sr, sc) == (er, ec):
        yield path
    else:
        for possible_path in search(sr+1, sc, er, ec, list(path)):
            yield possible_path
        for possible_path in search(sr-1, sc, er, ec, list(path)):
            yield possible_path
        for possible_path in search(sr, sc+1, er, ec, list(path)):
            yield possible_path
        for possible_path in search(sr, sc-1, er, ec, list(path)):
            yield possible_path

如果你想从 (0,1) 到 (3,3)：

print list(search(0, 1, 3, 3, []))

输出：

[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 3)]
[(0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 1), (0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
[(0, 1), (0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (3, 3)]

Answer 2

插入一个

grid[sx][sy] = 0

当您再次删除[sx, sy]from 路径（即在 之前return）以将该单元格标记为未再次访问时。

此外，您可能想要更改线路

solution.append(path)

至

solution.append(path[:])

创建该解决方案的副本以供以后使用。没有[:]您只需添加对同一列表的另一个引用，该列表稍后会在此过程中更改，以便您最终得到一个空列表列表solution。

并且您应该考虑不使用全局变量。我认为yield从生成器中找到的每个解决方案都比将其附加到全局变量要好得多。但这是一个不同的方面，在这里有点超出范围。