华为机试 BFS迷宫样题

华为机试 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():# 读取全部输入linessys.stdin.read().splitlines()idx0# 第一行读取行列rows,colsmap(int,lines[idx].split())idx1# 构建迷宫grid[]for_inrange(rows):rowlist(map(int,lines[idx].split()))grid.append(row)idx1# 上下左右四个方向dirs[(-1,0),(1,0),(0,-1),(0,1)]# 标记是否访问过防止回头重复走visited[[False]*colsfor_inrange(rows)]qdeque()# 起点(0,0)起点距离1ifgrid[0][0]1:# 起点就是墙直接不可达print(-1)returnq.append((0,0,1))visited[0][0]Truewhileq:x,y,stepq.popleft()# 判断是否走到终点ifxrows-1andycols-1:print(step)return# 遍历4个方向fordx,dyindirs:nxxdx nyydy# 判断边界nx、ny不越界不是墙没有访问过if0nxrowsand0nycols:ifgrid[nx][ny]0andnotvisited[nx][ny]:visited[nx][ny]Trueq.append((nx,ny,step1))# 队列空终点无法到达print(-1)if__name____main__:main()核心BFS原理费曼一句话BFS是一层一层向外扩散最先到达终点的路径一定是最短路径。适合迷宫最短路径问题。✅ BFS必须用deque.popleft()不要list pop(0)大数据会超时关键细节机试坑点visited访问标记一定要标记不然会重复入队死循环边界判断0 nx rows and 0 ny cols顺序不要写反起点本身是墙的边界case要提前处理路径长度定义要看题目有的题目步数移动次数起点不算样例输出为4按需修改初始step0# 如果题目要求步数移动次数移动几步起点不算q.append((0,0,0))方向数组dirs4方向不要写斜向(1,1)除非题目允许变体快速修改机试换题直接改这几行允许8方向上下左右四个斜角dirs[(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]迷宫字符版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如果你想要我可以给DFS迷宫版本求全部路径不是最短带记录路径坐标的BFS版本输出走过的坐标