python回溯算法走迷宫
时间: 2023-11-29 15:46:52 浏览: 43
以下是使用Python实现回溯算法走迷宫的示例代码:
```python
maze = [[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 1, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 0, 0],
[0, 1, 1, 1, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 0, 1, 0, 0]]
def solve_maze(x, y):
if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]):
return False
if maze[x][y] == 1:
return False
if x == len(maze) - 1 and y == len(maze[0]) - 1:
return True
maze[x][y] = 1
if solve_maze(x + 1, y):
return True
if solve_maze(x - 1, y):
return True
if solve_maze(x, y + 1):
return True
if solve_maze(x, y - 1):
return True
maze[x][y] = 0
return False
if solve_maze(0, 0):
for row in maze:
print(row)
else:
print("No solution found")
```
该代码使用二维列表表示迷宫,其中0表示通道,1表示墙壁。solve_maze函数使用递归实现回溯算法,从起点开始尝试向四个方向走,如果能够到达终点则返回True,否则返回False。如果找到了一条通往终点的路径,则将该路径上的所有点标记为1,并输出迷宫的解决方案。如果没有找到通往终点的路径,则输出"No solution found"。