采用递归算法求解迷宫问题,并输出从入口到出口的所有迷宫路径。
时间: 2023-08-21 18:01:37 浏览: 121
递归法解决迷宫问题
5星 · 资源好评率100%
好的,下面是递归算法求解迷宫问题的 Python 代码实现:
```python
maze = [[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]]
def solve_maze(x, y, path):
if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == 1:
# 超出边界或者是墙壁
return False
# 添加当前位置到路径中
path.append((x, y))
if x == len(maze) - 1 and y == len(maze[0]) - 1:
# 到达终点
print(path)
return True
# 尝试向上下左右四个方向寻找路线
if solve_maze(x + 1, y, path) or solve_maze(x - 1, y, path) or \
solve_maze(x, y + 1, path) or solve_maze(x, y - 1, path):
return True
# 四个方向都走不通,回溯
path.pop()
return False
solve_maze(0, 0, [])
```
其中,变量 `maze` 是一个二维数组,表示迷宫的布局,0 表示可以通过的通路,1 表示墙壁。`solve_maze` 函数采用递归算法来寻找迷宫通路,其中 `x` 和 `y` 表示当前位置的坐标,`path` 列表表示当前已经走过的路径。如果当前位置超出边界或者是墙壁,则返回 False;如果当前位置是终点,则输出路径并返回 True;否则,尝试向上下左右四个方向寻找路线,如果有一条路线能够找到终点,则返回 True,否则回溯并返回 False。最后,调用 `solve_maze` 函数,并传入起点坐标 `(0, 0)` 和空路径列表 `[]`,即可输出所有的迷宫路径。
阅读全文