穷举求解迷宫问题的代码
时间: 2024-06-24 19:00:50 浏览: 14
穷举法求解迷宫问题是一种简单直接的方法,通常通过遍历所有可能的路径来找到从起点到终点的解决方案。以下是一个基本的Python代码示例,使用深度优先搜索(DFS)策略:
```python
# 定义一个迷宫矩阵,0表示可以通行,1表示墙壁
maze = [
[0, 0, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 0]
]
# 假设 maze 是起点,maze[-1][-1] 是终点
def is_valid(maze, x, y):
return 0 <= x < len(maze) and 0 <= y < len(maze) and maze[x][y] == 0
def solve_maze(maze, x=0, y=0, path=[]):
if x == len(maze) - 1 and y == len(maze[0]) - 1: # 到达终点
return path + [(x, y)]
path.append((x, y))
# 检查所有可行的下一步
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # 上下左右
nx, ny = x + dx, y + dy
if is_valid(maze, nx, ny):
new_path = solve_maze(maze, nx, ny, path)
if new_path:
return new_path
# 如果没有找到路径,回溯到上一步
path.pop()
return []
# 打印所有可能的路径
solution = solve_maze(maze)
if solution:
print("Path found:", solution)
else:
print("No path found.")
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)