牛客网 HJ43 迷宫问题

牛客网 HJ43 迷宫问题题目链接https://www.nowcoder.com/practice/cf24406056f448c9dd51270e36174eec一、原题完整陈述题目描述定义一个N*M二维数组迷宫1代表墙壁不能通行0代表通路可以走。只能上下左右四个方向移动不能斜着走。起点左上角坐标(0,0)终点右下角坐标(N-1, M-1)。寻找从起点走到终点的路径题目保证存在唯一一条通路。本题有多组输入。输入描述第一行两个整数 N行数、M列数后面N行每行M个数字0或1空格隔开代表迷宫地图范围2 ≤ N,M ≤ 10输出描述按行走顺序每行输出路径上一个坐标格式(x,y)样例输入5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0样例输出(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)二、费曼学习法拆解破解思路讲给小白人话翻译你面前一张网格迷宫墙是1路是0。从左上角走到右下角只能上下左右走。我们要找到一条路线一步一步输出经过的坐标。两种经典方法DFS深度优先搜索和BFS广度优先搜索DFS一条路一直往前冲遇到死胡同就回头回溯适合找任意一条通路本题用DFS最简单机考写得快BFS一圈一圈向外扩散专门用来找最短路径本题题目说只有唯一路径两种方法都可以。DFS思路推荐机考站在当前格子标记已经走过防止来回兜圈重复走判断如果已经走到终点 → 找到路径返回True依次尝试四个方向下、右、上、左顺序会影响路径但本题唯一解新坐标不能越出迷宫边界新格子必须是通路0并且没有访问过如果往这个方向走递归进去探索递归返回True代表找到终点找到终点把当前坐标存入路径列表一层层返回回溯如果这个方向走不通取消标记尝试下一个方向回溯含义这条路走到底是死胡同退回来试别的分支。关键点访问标记走过的格子要标记不然会原地循环死递归坐标边界校验不能走到负数不能超过行数、列数路径存储递归是从终点往回收集坐标最后反转列表得到起点到终点顺序ACM模式多组输入循环读取直到EOF结束手动模拟小样例5*5样例起点(0,0)标记已访问尝试向下走到(1,0)再向下走到(2,0)(2,0)向右走到(2,1)继续向右走到(2,2)、(2,3)、(2,4)向下走到(3,4)再向下走到终点(4,4)。收集路径是倒序(4,4) → (3,4) → … → (0,0)反转后就是输出顺序。坑点忘记标记访问无限递归栈溢出坐标x代表行y代表列很多人xy写反路径收集顺序搞反输出坐标颠倒多组输入不加try-except捕获EOFError牛客OJ报错BFS思路补充找最短路径BFS用队列一层一层向外扩散。BFS需要额外保存每个格子的前驱坐标找到终点后从终点反向回溯到起点再反转得到完整路径。BFS天然保证路径最短DFS只是找到一条通路不保证最短。本题唯一通路结果一样。三、解法1DFS回溯解法机考首选Python完整代码 逐行注释# HJ43 迷宫问题 DFS回溯解法# 全局变量存储最终路径path[]defdfs(x,y,maze,rows,cols,visited):# x当前行坐标y当前列坐标# maze迷宫地图rows总行数cols总列数# visited标记格子是否已经访问过# 递归终止条件到达右下角终点(rows-1, cols-1)ifxrows-1andycols-1:# 到达终点把终点坐标加入路径path.append((x,y))returnTrue# 标记当前格子已经访问避免重复走、死循环visited[x][y]True# 四个移动方向下、右、上、左顺序可以调整directions[(1,0),(0,1),(-1,0),(0,-1)]# 遍历四个方向fordx,dyindirections:# 计算新坐标nxxdx nyydy# 判断新坐标是否在迷宫范围内行0~rows-1列0~cols-1if0nxrowsand0nycols:# 判断新格子是通路0并且没有访问过ifmaze[nx][ny]0andnotvisited[nx][ny]:# 递归探索新坐标如果返回True说明找到终点ifdfs(nx,ny,maze,rows,cols,visited):# 找到终点把当前坐标加入路径path.append((x,y))returnTrue# 四个方向全部走不通回溯取消当前格子访问标记visited[x][y]False# 这条路不通返回False回到上一层继续试别的方向returnFalsedefmain():globalpath# ACM模式多组输入循环读取直到没有输入whileTrue:try:# 每次新迷宫清空路径列表path[]# 读取行数N列数MN,Mmap(int,input().split())# 定义迷宫二维列表maze[]for_inrange(N):# 读取一行分割转整数列表存入迷宫rowlist(map(int,input().split()))maze.append(row)# 初始化访问标记二维数组全部False代表未访问visited[[False]*Mfor_inrange(N)]# 启动DFS起点(0,0)dfs(0,0,maze,N,M,visited)# path里面坐标是【终点倒序】需要反转变成起点→终点顺序path.reverse()# 遍历路径按规定格式输出 (x,y)forposinpath:print(f({pos[0]},{pos[1]}))# 捕获EOFError读到输入末尾退出循环程序结束exceptEOFError:break# 程序入口if__name____main__:main()解法2BFS广度优先搜索求最短路径版本逐行注释# HJ43迷宫 BFS广度优先搜索记录前驱节点回溯得到路径fromcollectionsimportdequedefmain():whileTrue:try:# 读取行数、列数N,Mmap(int,input().split())maze[]for_inrange(N):rowlist(map(int,input().split()))maze.append(row)# 标记是否访问visited[[False]*Mfor_inrange(N)]# pre记录每个坐标的前驱点用来回溯路径初始Nonepre[[None]*Mfor_inrange(N)]# 四个方向下 右 上 左directions[(1,0),(0,1),(-1,0),(0,-1)]# 队列BFS起点(0,0)入队qdeque()q.append((0,0))visited[0][0]True# BFS循环队列不为空持续搜索whileq:# 从队首取出当前坐标x,yq.popleft()# 如果到达终点跳出BFS循环ifxN-1andyM-1:break# 遍历四个方向fordx,dyindirections:nxxdx nyydy# 判断边界通路未访问if0nxNand0nyMandmaze[nx][ny]0andnotvisited[nx][ny]:visited[nx][ny]True# 记录(nx,ny)的前驱是(x,y)pre[nx][ny](x,y)# 新坐标入队q.append((nx,ny))# 从终点反向回溯构建路径path[]cur(N-1,M-1)whilecurisnotNone:path.append(cur)curpre[cur[0]][cur[1]]# 反转变成起点到终点顺序path.reverse()# 输出坐标forposinpath:print(f({pos[0]},{pos[1]}))exceptEOFError:breakif__name____main__:main()两个代码测试样例输入输出完全一致。四、应用场景举例场景1机器人室内导航最典型扫地机器人、巡检机器人室内环境用网格地图建模障碍物墙空地0。机器人从起点到目标点位DFS/BFS搜索可行路径。BFS优先用于最短移动路径规划减少行走距离。场景2游戏地图寻路RPG、像素游戏地图格子地图障碍物树木、墙。角色移动寻路简单小地图用DFS大型地图A*BFS的优化。场景3管道线路规划管网网格模型寻找一条从起点到出口的管线铺设路线避开障碍物。场景4二维网格逃生路线火灾模拟建筑网格化障碍物是墙体搜索逃生通道。场景5PCB电路板布线电路板网格不能穿过元器件墙寻找导线的可行布线路径。五、费曼复盘总结HJ43迷宫问题是网格图搜索。DFS一路向前走不通就回溯适合找到任意一条通路代码简短不保证最短路径。BFS队列一层一层扩散一定找到最短路径需要额外存储前驱坐标来还原完整路径。核心要点四个方向遍历边界校验访问标记防止环路死循环路径收集递归BFS拿到的路径是逆序必须反转ACM多组输入捕获EOFError知识点深度优先DFS、回溯、广度优先BFS、队列、二维网格图搜索复杂度分析设网格 N行M列总格子数量SN×MSN\times MSN×MDFS时间O(NM)O(NM)O(NM)每个格子最多访问一次空间O(NM)O(NM)O(NM)递归栈visited数组BFS时间O(NM)O(NM)O(NM)每个格子入队一次空间O(NM)O(NM)O(NM)队列visitedpre前驱数组