用队列实现迷宫问题 ,BF算法的实现,写出运行代码
时间: 2024-10-14 18:08:28 浏览: 9
用队列实现迷宫问题通常涉及到广度优先搜索(Breadth-First Search,简称 BFS),这是一种用于遍历或寻找最短路径的算法。在迷宫问题中,我们从起点开始,每次从队列中取出一个节点并探索其周围的邻居,如果邻居是空格且未访问过,则标记为已访问并将它加入队列。这个过程一直持续到找到终点或者队列为空。
BFS的步骤简述如下:
1. 将起始位置放入队列。
2. 创建一个集合或数组记录已经访问过的节点,防止重复访问。
3. 当队列非空时,循环执行以下操作:
- 取出队首位置。
- 检查当前位置是否是终点;如果是,返回路径。
- 否则,检查相邻的节点(上、下、左、右),若未访问并且是空格,添加到队列,并标记为已访问。
4. 如果找不到路径,说明迷宫中无解或路径太长。
以下是Python的一个简单示例,使用`deque`作为队列:
```python
from collections import deque
def bfs(maze, start, end):
queue = deque([(start, [start])])
visited = set([start])
while queue:
current, path = queue.popleft()
if current == end:
return path
for neighbor in [(current[0] + 1, current[1]), (current[0], current[1] + 1), # 上下左右
(current[0] - 1, current[1]), (current[0], current[1] - 1)]: # 同理加减一处理边界
if 0 <= neighbor[0] < len(maze) and 0 <= neighbor[1] < len(maze[0]) and maze[neighbor[0]][neighbor[1]] == 0 and neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
# 示例迷宫,1表示墙壁,0表示通道,S和E分别代表起始点和结束点
maze = [[1, 0, 0, 1],
[1, 0, 1, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
start = (0, 0) # 起点
end = (3, 3) # 终点
path = bfs(maze, start, end)
if path:
print(f"找到了路径:{path}")
else:
print("无法到达目标")
```
阅读全文