企业官网建设流程全解析

华为机试 BFS迷宫样题（Python，可直接提交AC完整代码）

题目描述（经典迷宫最短路径，华为机试高频）

给定一个二维迷宫，0代表通路，1代表墙壁不能走。
起点在左上角(0,0)，终点在右下角(rows-1, cols-1)。
每次只能上下左右4个方向移动，不能斜走。
求从起点到终点的最短路径长度；无法到达输出-1。

路径长度定义：走过的格子数量（起点算第1步）

输入描述
第一行两个数字：rows cols，代表迷宫行数、列数
后面rows行，每行若干数字（0/1，空格分隔），代表迷宫

输入样例

3 3 0 0 0 0 1 0 0 0 0

输出样例

5

解释：(0,0) → (0,1) → (0,2) → (1,2) → (2,2)，一共5格

完整可提交代码（牛客华为OJ直接粘贴）

importsysfromcollectionsimportdequedefmain():# 读取全部输入lines=sys.stdin.read().splitlines()idx=0# 第一行读取行列rows,cols=map(int,lines[idx].split())idx+=1# 构建迷宫grid=[]for_inrange(rows):row=list(map(int,lines[idx].split()))grid.append(row)idx+=1# 上下左右四个方向dirs=[(-1,0),(1,0),(0,-1),(0,1)]# 标记是否访问过，防止回头重复走visited=[[False]*colsfor_inrange(rows)]q=deque()# 起点(0,0)，起点距离=1ifgrid[0][0]==1:# 起点就是墙，直接不可达print(-1)returnq.append((0,0,1))visited[0][0]=Truewhileq:x,y,step=q.popleft()# 判断是否走到终点ifx==rows-1andy==cols-1:print(step)return# 遍历4个方向fordx,dyindirs:nx=x+dx ny=y+dy# 判断边界：nx、ny不越界；不是墙；没有访问过if0<=nx<rowsand0<=ny<cols:ifgrid[nx][ny]==0andnotvisited[nx][ny]:visited[nx][ny]=Trueq.append((nx,ny,step+1))# 队列空，终点无法到达print(-1)if__name__=="__main__":main()

核心BFS原理（费曼一句话）

BFS是一层一层向外扩散，最先到达终点的路径一定是最短路径。适合迷宫最短路径问题。

✅ BFS必须用deque.popleft()，不要list pop(0)，大数据会超时！

关键细节（机试坑点）

1. visited访问标记：一定要标记，不然会重复入队死循环
2. 边界判断：0 <= nx < rows and 0 <= ny < cols，顺序不要写反
3. 起点本身是墙的边界case，要提前处理
4. 路径长度定义要看题目！有的题目步数=移动次数（起点不算，样例输出为4），按需修改初始step=0

# 如果题目要求：步数=移动次数（移动几步，起点不算）q.append((0,0,0))

5. 方向数组dirs：4方向，不要写斜向(1,1)除非题目允许

变体快速修改（机试换题直接改这几行）

1. 允许8方向（上下左右+四个斜角）

dirs=[(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

2. 迷宫字符版（S起点，E终点，#墙，.通路）

• 判断条件改成：grid[nx][ny] != '#'
• 找到S作为起点，E作为终点

自测方法

复制输入：

3 3 0 0 0 0 1 0 0 0 0

运行输出：5

测试不可达案例
输入：

2 2 0 1 1 0

输出：-1

如果你想要，我可以给：

1. DFS迷宫版本（求全部路径，不是最短）
2. 带记录路径坐标的BFS版本（输出走过的坐标）