本文详解为何朴素dfs在“球滚动迷宫”类问题中无法保证最短路径，指出状态定义缺陷（未区分入向方向），并给出带方向感知的dfs优化方案及剪枝技巧。
本文详解为何朴素dfs在“球滚动迷宫”类问题中无法保证最短路径，指出状态定义缺陷（未区分入向方向），并给出带方向感知的dfs优化方案及剪枝技巧。
在解决类似 LeetCode 505. Maze II 的滚动球最短路径问题时，许多初学者会本能地选择 DFS——毕竟它逻辑直观：从起点出发，沿四个方向持续滚动直至撞墙，再递归探索新停点。但正如示例代码所示，简单使用二维 `visited[i][j]` 标记已访问坐标会导致严重错误：**同一位置 `(i, j)` 可能从不同方向到达，对应不同的累计距离和后续可行路径，而二维 visited 会过早阻断更优路径**。例如，在给定测试用例中，球从 (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 <p>该策略天然避免重复探索高成本路径，显著提升效率，也无需回溯操作。</p><h3>⚠️ 注意事项与对比说明</h3>
- 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 才能在滚动迷宫中稳定收敛至最优解。
