dfs迷宫输出所有路径
时间: 2023-06-24 09:04:04 浏览: 113
深度优先搜索(DFS)是一种常用的图遍历算法,可以用来解决迷宫问题。下面是一种基于DFS的求解迷宫所有路径的算法:
1. 定义一个二维数组maze表示迷宫,其中0表示可走的路,1表示墙,2表示已经走过的路。
2. 定义一个栈stack,用来存储走过的路径。
3. 定义一个列表paths,用来存储所有走过的路径。
4. 定义一个函数dfs(x, y)表示从坐标为(x, y)的位置开始走迷宫。
5. 在函数dfs(x, y)中,如果当前位置为终点,则将stack中的路径添加到paths中,并返回。
6. 如果当前位置不是终点,则将当前位置标记为已经走过,然后按照上、右、下、左的顺序依次尝试往下一个位置走。
7. 如果下一个位置是可走的路,则将其入栈,并递归调用dfs函数继续走迷宫。
8. 如果下一个位置已经走过或者是墙,则不再尝试走这个方向。
9. 最后,将当前位置标记为未走过,将stack中的最后一个位置弹出,表示回溯到上一步。
下面是Python代码实现:
```python
maze = [
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 0, 0, 0]
]
stack = [(0, 0)]
paths = []
def dfs(x, y):
if x == len(maze) - 1 and y == len(maze[0]) - 1:
paths.append(list(stack))
return
maze[x][y] = 2
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == 0:
stack.append((nx, ny))
dfs(nx, ny)
stack.pop()
maze[x][y] = 0
dfs(0, 0)
for path in paths:
print(path)
```
以上代码输出所有从起点到终点的路径。