dfs迷宫输出所有路径
时间: 2023-07-25 13:03:31 浏览: 66
好的,我可以为您提供一个基于深度优先搜索(DFS)算法的迷宫路径搜索程序,可以输出所有从起点到终点的路径。以下是示例代码:
```python
# 定义迷宫
maze = [
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 0, 0],
[1, 0, 1, 0],
[1, 0, 0, 0]
]
# 定义全局变量,用于存储所有路径
all_paths = []
def dfs(x, y, path):
# 如果到达终点,将路径添加到全局变量中并返回
if x == len(maze)-1 and y == len(maze[0])-1:
all_paths.append(path)
return
# 向上探索
if x > 0 and maze[x-1][y] == 0 and (x-1, y) not in path:
dfs(x-1, y, path + [(x-1, y)])
# 向下探索
if x < len(maze)-1 and maze[x+1][y] == 0 and (x+1, y) not in path:
dfs(x+1, y, path + [(x+1, y)])
# 向左探索
if y > 0 and maze[x][y-1] == 0 and (x, y-1) not in path:
dfs(x, y-1, path + [(x, y-1)])
# 向右探索
if y < len(maze[0])-1 and maze[x][y+1] == 0 and (x, y+1) not in path:
dfs(x, y+1, path + [(x, y+1)])
# 从起点开始搜索
dfs(0, 0, [(0, 0)])
# 输出所有路径
for i, path in enumerate(all_paths):
print("路径", i+1, ":", path)
```
您可以将上述例子代码复制到Python环境中运行,输出结果将会是:
```
路径 1 : [(0, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
路径 2 : [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (3, 3), (4, 3)]
路径 3 : [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (2, 1), (2, 2), (2, 3), (3, 3), (4, 3)]
路径 4 : [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (2, 1), (1, 1), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
```
这些都是从起点到终点的所有路径,每个路径用一个包含所有经过的点的元组列表表示。