Python 迷宫 BFS 算法实现

from collections import deque

def bfs(maze, start, end): # 迷宫大小 rows, cols = len(maze), len(maze[0]) # 准备方向向量，表示四个可能移动的方向，上 右 下 左 directions = [(0, -1), (0, 1), (-1, 0), (1, 0)] queue = deque([start]) # 初始化队列，开始位置入队 visited = set() # 记录已访问的节点 while queue: # 取出队列首部的元素 cur_pos = queue.popleft() # 如果当前位置是终点，返回路径 if cur_pos == end: path = [] while cur_pos != start: path.append(cur_pos) cur_pos = (cur_pos[0] + directions[cur_pos[1]][0], cur_pos[1] + directions[cur_pos[1]][1]) path.append(start) path.reverse() return path # 标记当前位置已访问过 visited.add(cur_pos) # 检查四个方向是否可以移动 for direction in directions: next_pos = (cur_pos[0] + direction[0], cur_pos[1] + direction[1]) # 检查新位置是否在迷宫范围内并且是没有访问过的，并不是墙壁 if 0 <= next_pos[0] < rows and 0 <= next_pos[1] < cols and next_pos not in visited and maze[next_pos[0]][next_pos[1]] != 1: queue.append(next_pos) # 新位置入队 return None # 没有找到路径

maze = [ [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0], ] start = (0, 0) end = (4, 4) print(bfs(maze, start, end))