DFS求解迷宫最短路径常见误区及正确实现方法

在挑战LeetCode 505 Maze II这类滚动球最短路径问题时，许多开发者第一反应就是选用DFS——从起点出发沿四个方向持续滚动直至撞墙，再递归探索新停点，逻辑确实直观。但其中隐藏着一个关键陷阱：简单采用二维visited[i][j]标记已访问坐标，往往导致严重偏差。同一位置(i,j)从不同方向抵达时，累计距离与后续可行路径可能完全不同，而二维visited数组会过早屏蔽更优路径。

本文深入剖析朴素DFS在“球滚动迷宫”类问题中无法保证最短路径的根本原因，揭示状态定义缺陷（未区分入向方向），并给出带方向感知的DFS优化方案及高效剪枝技巧。

以标准测试用例为例，球从(0,4)出发，最优路径长度为12；但原始DFS因在(2,2)处被过早标记为已访问（无论是从上方还是左方进入），导致绕行更远路径，最终输出16。这类错误在迷宫最短路径求解中十分典型，根源在于状态建模的维度缺失。

✅ 正确状态建模：三维visited数组与方向感知策略

核心修正在于将“状态”定义为(行, 列, 入向方向)三元组，而非简单的(行, 列)二元组。原因在于：球停驻于(i,j)时，其上一轮的滚动方向直接决定了后续可滚动的方向集——例如刚从上方滚入，便不能立即回弹向上，但可以向左、向右或向下继续滚动。因此需为每个坐标维护4个方向的独立访问记录：

boolean[][][] visited = new boolean[maze.length][maze[0].length][4]; // [i][j][k]: 是否以第k个方向到达(i,j)

需特别注意：不应在进入递归前全局标记visited[i][j][k] = true，而应在确认滚动终点(x,y)后，针对来向方向k进行标记。若采用回溯式DFS，还须在递归返回后执行回溯。更推荐的做法是使用距离数组替代布尔数组，从而自然实现剪枝效果，避免冗余探索。

✅ 高效剪枝：基于最小距离的动态状态更新策略

更高效的实现方式是用int[][][] dist数组替代visited。dist[i][j][k]记录以方向k滚入位置(i,j)所需的最小步数。每次计算出新路径长度newcount后，仅当newcount小于当前记录时，才继续递归探索：

if (newcount < visited[x][y][k]) {    visited[x][y][k] = newcount;    dfs(maze, x, y, destination, visited, newcount);}

该策略天然避免了重复探索高成本路径，效率显著提升且无需回溯操作，在迷宫规模较大时优势尤为明显。

⚠️ 注意事项与方案对比

• BFS仍是最优方案：该问题本质是无权图上的最短路径搜索（边权即为滚动步数），Dijkstra算法或基于优先队列的BFS能自然保证首次抵达即为最优解，代码更简洁且逻辑更鲁棒。DFS+剪枝虽可行但易出错，扩展性相对较弱。
• 方向索引一致性：假设dirs = {{-1,0},{1,0},{0,-1},{0,1}}分别对应上、下、左、右，必须确保方向索引k与dirs[k]严格对应，否则状态将陷入混乱，导致路径计算错误。
• 边界与障碍判断：在滚动while循环中，需检查maze[x + dir[0]][y + dir[1]] == 0，即仅当目标格子为空时方可继续滚动，才能准确模拟“不撞墙不停”的物理规则，确保路径探索的完整性。

综上所述，采用DFS解决这类最短路径问题的关键在于状态建模的完备性与剪枝策略的有效性，而非“深度优先”本身。只有将方向维度纳入状态空间，并以距离为判据动态淘汰劣质分支，DFS才能在滚动迷宫问题中稳定输出最优解，为后续优化算法提供可靠基础。