回溯算法求解迷宫问题python
时间: 2023-12-02 12:43:19 浏览: 38
以下是使用回溯算法求解迷宫问题的Python代码:
```python
def solve_maze(maze):
# 定义一个二维数组,用于记录路径
solution = [[0] * len(maze) for _ in range(len(maze))]
# 定义一个列表,用于记录路径
path = []
# 调用回溯函数
if backtrack(maze, 0, 0, solution, path):
return path
else:
return "No solution found"
def backtrack(maze, row, col, solution, path):
# 如果到达了终点,返回True
if row == len(maze) - 1 and col == len(maze) - 1:
solution[row][col] = 1
path.append((row, col))
return True
# 如果当前位置可以走
if is_valid(maze, row, col):
# 标记当前位置已经走过
solution[row][col] = 1
# 将当前位置加入路径
path.append((row, col))
# 向下走
if backtrack(maze, row + 1, col, solution, path):
return True
# 向右走
if backtrack(maze, row, col + 1, solution, path):
return True
# 如果都走不通,回溯
solution[row][col] = 0
path.pop()
return False
def is_valid(maze, row, col):
# 判断当前位置是否越界或者已经走过或者当前位置为0
if row < 0 or col < 0 or row >= len(maze) or col >= len(maze) or maze[row][col] == 0:
return False
return True
```