通过迷宫找到路径-Java 学习之路

我希望在迷宫中找到明显可能的路径从开始到结束点我已编写代码但它只给我一些迷宫中的路径...我想要所有路径请给出一些建议

2 回答

使用发电机的解决方案

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

回复于 2024-04-28T02:26:48+08:00

3
插入一个
```
grid[sx][sy] = 0
```
当您再次从路径中删除 [sx, sy] 时（即在 return 之前），以便将该单元格标记为未再次访问 .

此外，您可能想要更改该行
```
solution.append(path)
```
至
```
solution.append(path[:])
```
创建该解决方案的副本，以便以后保留它 . 如果没有 [:] ，您只需添加对同一列表的另一个引用，该列表稍后会在此过程中更改，以便您最终得到 solution 中的空列表列表 .

你应该考虑不使用全局变量 . 我想 yield 每个从发生器找到的解决方案比将它附加到全局变量要好得多 . 但这是一个不同的方面，有点超出范围 .
回复于 2024-04-28T02:26:48+08:00

通过迷宫找到路径

2 回答

相关问题