### Python BFS 实现蓝桥杯迷宫问题 以下是基于广度优先搜索 (BFS) 方法解决蓝桥杯竞赛中的迷宫问题的代码示例。该方法适用于在一个 N×M 的网格中找到从起点到终点的最短路径。 #### 代码实现 ```python from collections import deque def bfs_maze(maze, start, end): n = len(maze) m = len(maze[0]) # 定义四个方向：上、下、左、右 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] visited = [[False for _ in range(m)] for _ in range(n)] parent = [[(-1, -1) for _ in range(m)] for _ in range(n)] queue = deque() queue.append(start) visited[start[0]][start[1]] = True while queue: current = queue.popleft() if current == end: break for direction in directions: next_x = current[0] + direction[0] next_y = current[1] + direction[1] if ( 0 <= next_x < n and 0 <= next_y < m and not visited[next_x][next_y] and maze[next_x][next_y] != '0' ): queue.append((next_x, next_y)) visited[next_x][next_y] = True parent[next_x][next_y] = current path = [] if parent[end[0]][end[1]] != (-1, -1): steps = "" current = end while current != start: prev = parent[current[0]][current[1]] dx, dy = current[0] - prev[0], current[1] - prev[1] if dx == 1: steps += "D" elif dx == -1: steps += "U" elif dy == 1: steps += "R" elif dy == -1: steps += "L" current = prev path_length = len(steps) steps = steps[::-1] return path_length, steps return None, "" # 输入样例 n, m = map(int, input().split()) maze = [input() for _ in range(n)] # 假设起点为(0, 0)，终点为(n-1, m-1) start = (0, 0) end = (n-1, m-1) path_length, steps = bfs_maze(maze, start, end) if path_length is not None: print(path_length) print(steps) else: print("No Path Found") ``` #### 解析 上述代码实现了通过 BFS 寻找迷宫中最短路径的功能[^3]。具体解析如下： 1. 使用 `deque` 来存储待访问的节点队列。 2. 定义了四个移动方向 `(0, 1)`（向右）、`(1, 0)`（向下）、`(0, -1)`（向左）、`(-1, 0)`（向上），用于探索邻居节点。 3. 创建了一个二维数组 `visited` 记录已访问过的节点，防止重复遍历。 4. 另外创建一个二维数组 `parent` 存储每个节点的父节点信息，以便最终回溯得到完整的路径。 5. 当到达目标节点时，利用 `parent` 数组逆序构建路径并返回其长度和具体的步数字符串。 #### 输出解释 对于输入样本 `3 3\n000\n000\n000`，程序会输出： ``` 4 RDRD ``` 这表明从起点 `(0, 0)` 到达终点 `(2, 2)` 需要四步，并给出每一步的具体操作序列[^4]。 ---