广度优先搜索迷宫代码
时间: 2024-06-23 22:00:58 浏览: 77
当然,广度优先搜索(Breadth-First Search, BFS)是一种常用算法,用于解决迷宫问题,寻找从起点到终点的最短路径。下面是一个基本的Python代码示例,使用邻接矩阵表示迷宫:
```python
from collections import deque
# 假设maze是一个二维列表,值为0表示可以通过,1表示墙壁
def bfs(maze, start, end):
if start == end: # 如果起点和终点相同,直接返回True
return True
if not maze[start][start]: # 如果起始点无法到达
return False
visited = set() # 记录已访问过的节点
queue = deque([(start, [])]) # 用队列存储待探索的节点和路径
while queue:
node, path = queue.popleft()
visited.add(node) # 标记节点为已访问
if node == end: # 找到了目标节点
return True
for neighbor in get_neighbors(maze, node): # 获取相邻节点
if neighbor not in visited and maze[neighbor][neighbor] == 0: # 只有相邻且未访问的节点才加入队列
queue.append((neighbor, path + [node]))
return False # 如果遍历完队列都没有找到,说明无解
def get_neighbors(maze, node):
row, col = node
neighbors = [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]
return [n for n in neighbors if 0 <= n < len(maze) and 0 <= n < len(maze)]
# 使用方法
maze = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[1, 1, 0, 0]
]
start = (0, 0)
end = (3, 3)
if bfs(maze, start, end):
print("找到了从起点到终点的路径")
else:
print("无解")
```