使用DFS正确求解迷宫球最短停止路径

本文将解析DFS算法在《Maze II》这类滚动球最短路径问题中容易踩的坑，以及如何利用状态去重与距离剪枝技巧来精准避免。

本文将详细讲解DFS算法在《Maze II》（LeetCode 505）滚动球最短路径问题中常见的陷阱，并介绍通过状态去重和距离剪枝来修复的方法。

在图论和搜索算法的实际应用中，许多开发者常有一个误区：认为只要遍历所有路径，DFS就一定能找到最短路径。这种直觉在静态网格中通常成立，但遇到《Maze II》（LeetCode 505）这类“滚动球”问题就容易出错。在本问题中，球一旦启动，会沿当前方向持续滚动直至撞墙停止。每个停止位置可视为一个状态节点，关键在于——从同一坐标以不同方向到达时，后续可行的路径可能截然不同。

原始代码失效的核心原因在于其状态定义过于简单：仅使用坐标 (i,j) 标记是否访问过，完全忽略了抵达方向这一关键信息。例如，球从上方进入格子 (2,2) 与从左侧进入 (2,2)，虽然位置相同，但后续的滚动方向和路径长度可能差异巨大。若仅用二维 visited 数组做判断，很容易将从左侧进入的更优路径误判为已访问而剪枝。这正是经典题目中错误实现输出16而正确答案为12的根本原因。

✅ 正确的做法是什么？ 将状态定义扩展为三维：visited[i][j][d]，其中 d 表示方向（通常0上、1下、2左、3右）。仅当以相同方向再次到达同一坐标时，才判定为重复状态，从而安全地进行剪枝。改进后的DFS代码示例如下：

private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][][] visited, int count) {
    if (i == destination[0] && j == destination[1]) {
        shortest = Math.min(shortest, count);
        return;
    }
    for (int k = 0; k < dirs.length; k++) {
        int[] dir = dirs[k];
        int x = i, y = j, newcount = count;
        // 沿当前方向持续滚动，直至撞墙
        while (x + dir[0] >= 0 && x + dir[0] < maze.length &&
               y + dir[1] >= 0 && y + dir[1] < maze[0].length &&
               maze[x + dir[0]][y + dir[1]] == 0) {
            x += dir[0];
            y += dir[1];
            newcount++;
        }
        // 仅当 (x,y) 以方向 k 首次到达时，才进入递归
        if (!visited[x][y][k]) {
            visited[x][y][k] = true;
            dfs(maze, x, y, destination, visited, newcount);
        }
    }
}

⚠️ 注意了，这里仍存在隐患。仅使用三维布尔数组并不能一劳永逸，因为 DFS 的遍历顺序不可预测，可能先找到一条较长路径并标记为已访问，从而排除后面更短的路径。根本原因在于 DFS 不保证首次到达某一状态时的距离是最优的。

因此，更严谨的优化方案是将 visited 改为 int[][][] minDist，用于存储以方向 k 到达 (i,j) 的最短距离。仅当新路径的距离更短时，才允许更新并继续递归，从而真正实现距离驱动的剪枝：

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

总结一下： 使用DFS求解最短路径，本质上是在对抗盲目回溯和重复探索。对于滚动球、滑冰者这类具有惯性运动特性的状态空间，必须将方向作为状态维度纳入建模。结合距离记录的剪枝策略，可以在保持DFS代码简洁的同时，使效率与逻辑接近Dijkstra算法。不过，从理论最优解的角度看，BFS（或优先队列优化的Dijkstra）才是这类加权图最短路径的标准解法。本文讨论的DFS优化版本，旨在帮助读者深入理解状态设计思路与剪枝技巧的巧妙之处。