python用队实现迷宫
时间: 2024-01-01 15:48:53 浏览: 67
基于Python实现迷宫求解【100011880】
解法,你能告诉我吗?
当解决迷宫的时候,深度优先搜索算法(DFS)和广度优先搜索算法(BFS)是常见的算法。使用队列的BFS算法是一种比较简单的实现方法,可以按照以下步骤进行:
1. 将起点入队列,将起点标记为已访问。
2. 当队列非空时,取队首元素a。
3. 通过a对应的位置向四个方向进行探索,如果该位置未曾访问且不是墙,则将该位置入队列,并标记为已访问。如果该位置是终点,则直接返回到步骤5。如果四个方向都没有未访问的位置,则返回到步骤2。
4. 重复步骤2-3,直到找到终点或者队列为空。
5. 找到终点后,可以根据每个位置所代表的状态,沿着已访问的路径逆推到起点,从而得到路径。
以下是一个Python实现的示例代码:
```python
from collections import deque
# 迷宫,用二维列表表示,0表示空位,1表示墙
maze = [
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
# 起点和终点
start = (1, 1)
end = (5, 5)
# 搜索路径
def bfs(maze, start, end):
# 将起点入队列,将起点标记为已访问
queue = deque([start])
visited = set([start])
# 方向数组,可以在四个方向移动
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while queue:
# 取队首元素a
cur_pos = queue.popleft()
# 已找到终点
if cur_pos == end:
return True
# 向四个方向进行探索
for dir in directions:
new_pos = (cur_pos[0]+dir[0], cur_pos[1]+dir[1])
if new_pos[0]<0 or new_pos[0]>=len(maze) or new_pos[1]<0 or new_pos[1]>=len(maze[0]):
continue
if maze[new_pos[0]][new_pos[1]]==1 or new_pos in visited:
continue
# 将该位置入队,并标记为已访问
queue.append(new_pos)
visited.add(new_pos)
# 无法到达终点
return False
if bfs(maze, start, end):
print("可到达")
else:
print("无法到达")
```
在这个示例代码中,`bfs`函数使用队列实现了BFS算法来进行迷宫路径搜索,如果找到了终点就返回`True`,否则就返回`False`。如果返回了`True`,则说明可以从起点到达终点,可以根据记录的路径反向输出来得到具体的路径。如果返回了`False`,则说明不可到达终点。
阅读全文