Python迷宫问题广度优先搜索算法求解代码
时间: 2023-11-03 10:12:35 浏览: 61
以下是Python实现的广度优先搜索算法求解迷宫问题的代码示例:
```python
from collections import deque
def bfs(maze, start, end):
queue = deque([(start, [])])
visited = set([start]) # 记录已经搜索过的位置
while queue:
curr_pos, path = queue.popleft()
if curr_pos == end:
return path + [end]
for direction in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
next_pos = (curr_pos[0]+direction[0], curr_pos[1]+direction[1])
if 0 <= next_pos[0] < len(maze) and 0 <= next_pos[1] < len(maze[0]) and \
maze[next_pos[0]][next_pos[1]] == 0 and next_pos not in visited:
queue.append((next_pos, path+[curr_pos]))
visited.add(next_pos)
return None # 无解
# 示例
maze = [[0, 0, 0, 1, 0],
[1, 0, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 1]]
start, end = (0, 0), (4, 4)
print(bfs(maze, start, end))
```
该代码使用了队列和集合作为数据结构,其中队列保存了当前正在遍历的节点和到达该节点的路径,集合保存了已经搜索过的节点,避免重复搜索。当搜索到终点时,返回到达该节点的路径,否则返回None表示无解。