怎样用 DFS 正确求解迷宫滚动球的最短路径问题
本文详解为何朴素 dfs 无法保证找到 maze ii 类滚动球问题的最短路径，并给出两种关键改进方案：基于方向状态的 visited 三维标记与带距离剪枝的动态更新机制。
本文详解为何朴素 dfs 无法保证找到 maze ii 类滚动球问题的最短路径，并给出两种关键改进方案：基于方向状态的 visited 三维标记与带距离剪枝的动态更新机制。
在图论与算法实践中，DFS（深度优先搜索）常被误用于求解“最短路径”问题——尤其在 LeetCode 的 Maze II 这类滚动球迷宫题中。题目要求球从起点出发，沿上下左右四个方向持续滚动直至撞墙停止，每次停驻点构成一个有效状态；目标是找到抵达终点的最小滚动步数（即经过的空格总数）。虽然 BFS 天然适配无权图最短路径，但许多开发者尝试用 DFS 实现，却屡次得到错误结果（如示例输入应输出 12，而原始代码返回 16）。根本原因在于：标准 DFS 缺乏对“同一位置不同进入方向”状态的区分能力，且未对非最优路径进行及时剪枝。
❌ 原始 DFS 的致命缺陷
原始实现使用二维 visited[i][j] 标记已访问坐标，一旦某坐标 (i, j) 被访问过，后续任何方向滚入该点都会被跳过。然而，在滚动模型中，从不同方向到达同一坐标，代表完全不同的状态——因为下一步可选的滚动方向受当前“来向”影响（例如，从上方滚入后不能立即向上反向滚动，但可向左/右/下继续），更重要的是：更晚到达某点的路径，可能对应更小的累计距离。二维 visited 粗暴阻断了所有后续可能性，导致更优路径被提前扼杀。
此外，原始代码在进入递归前未做任何距离判断，即使当前 count 已远超已知最优解，仍继续深搜，造成大量无效计算。
✅ 改进方案一：三维 visited —— 按“到达方向”精细化状态
关键洞察：每个停驻点 (x, y) 需记录 以哪个方向（0: 上，1: 下，2: 左，3: 右）滚入 时的访问状态。因此将 visited 升级为三维布尔数组 visited[x][y][dirIdx]：
boolean[][][] visited = new boolean[maze.length][maze[0].length][4];// 在 dfs 中检查并标记if (!visited[x][y][k]) { visited[x][y][k] = true; dfs(maze, x, y, destination, visited, newcount); visited[x][y][k] = false; // 回溯（若需复用状态）}
此设计确保：(2,3) 点从上方滚入（dirIdx=0）和从左侧滚入（dirIdx=2）被视为两个独立状态，互不干扰。这解决了状态覆盖问题，使 DFS 能探索所有合法路径分支。
✅ 改进方案二：距离驱动剪枝 —— 动态更新最优到达代价
更进一步，我们不仅需要知道“是否来过”，更要记录“以某方向到达 (x,y) 的最小步数”。于是将 visited 替换为 dist[x][y][dirIdx]，初始化为 Integer.MAX_VALUE：
int[][][] dist = new int[maze.length][maze[0].length][4];for (int i = 0; i < maze.length; i++) { for (int j = 0; j < maze[0].length; j++) { Arrays.fill(dist[i][j], Integer.MAX_VALUE); }}// 在 dfs 中剪枝if (newcount < dist[x][y][k]) { dist[x][y][k] = newcount; dfs(maze, x, y, destination, dist, newcount);}
该策略实现了 Dijkstra 式的距离松弛：仅当发现更短路径到达 (x,y) 的某个方向状态时，才继续递归。这大幅减少搜索空间，避免陷入长路径陷阱，是 DFS 求解最短路的核心优化。
⚠️ 注意事项与总结
- DFS ≠ 最短路径算法：除非辅以状态去重与距离剪枝，否则 DFS 仅保证可达性，不保证最优性。
- 状态定义决定正确性：滚动球问题的状态必须包含 (行, 列, 入口方向) 三元组，缺一不可。
- 剪枝优于回溯：在递归入口处用 if (newcount >= dist[x][y][k]) return; 直接剪枝，比回溯标记更高效。
- 实际推荐方案：尽管改进后 DFS 可行，但 Maze II 的本质是边权为正的无向图最短路径问题，优先选用 Dijkstra（堆优化）或 BFS（因边权恒为1，但注意：此处“边权”是滚动距离，非单位步，故严格需 Dijkstra）。DFS 改进版更多用于理解状态建模思想。
最终，正确实现的 DFS 不再是盲目遍历，而是以状态空间建模为基石、以距离优化为引擎的精确搜索——这正是图算法从“能跑通”迈向“可证明正确”的关键跃迁。
