本文深入剖析使用深度优先搜索（dfs）解决“球滚动迷宫最短距离”问题时的关键缺陷——状态定义不足导致重复探索与次优路径无法剪枝，并给出基于方向感知访问标记与距离记忆化的正确dfs实现方案。
本文深入剖析使用深度优先搜索（dfs）解决“球滚动迷宫最短距离”问题时的关键缺陷——状态定义不足导致重复探索与次优路径无法剪枝，并给出基于方向感知访问标记与距离记忆化的正确dfs实现方案。
在解决类似 LeetCode 505. The Maze II 这类“滚动球最短路径”问题时，初学者常误以为标准 DFS（仅以坐标 (i, j) 为状态）能自然收敛到最短路径。但该题的核心机制——球沿某一方向持续滚动直至撞墙才停止并可转向——使得同一位置 (i, j) 从不同方向到达，后续可行路径与剩余距离完全不同。原始代码中仅用二维 visited[i][j] 标记已访问坐标，会过早阻断更优路径：例如从上方滚入某点后标记为已访，但若之后从左侧以更小代价滚入该点，却被跳过，从而错过全局最优解。
根本问题在于：状态空间缺失方向维度。正确做法是将状态定义为三元组 (i, j, d)，其中 d ∈ {0,1,2,3} 表示球抵达 (i,j) 时的最后滚动方向（上/下/左/右）。只有当相同位置、相同入射方向的组合被更短距离访问过时，才可安全剪枝。
以下是修正后的 DFS 实现要点：
- ✅ 使用三维数组 visited[i][j][d] 记录以方向 d 到达 (i,j) 的最小累计距离；
- ✅ 每次滚动后，确定终点 (x,y) 及新距离 newcount；
- ✅ 仅当 newcount
- ✅ 移除全局 boolean[][] visited，避免粗粒度剪枝。
public class MazeII {
private int shortest = Integer.MAX_VALUE;
private final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int n = maze.length, m = maze[0].length;
// visited[i][j][d]: 以方向 d 到达 (i,j) 的最小距离
int[][][] visited = new int[n][m][4];
for (int i = 0; i = 0 && x + dir[0] = 0 && y + dir[1] <p>⚠️ 注意事项：</p>
- 单纯 DFS 仍可能遍历大量冗余路径，时间复杂度高于 BFS（后者天然按距离层级扩展，首次到达即最短）；
- 若追求最优性能，推荐改用 Dijkstra 算法（堆优化版），将 (i,j) 视为图节点，滚动终点为邻接点，边权为滚动步数，时间复杂度降至 O(V log V)；
- 本 DFS 方案适用于理解状态建模本质，但在大规模迷宫中需谨慎评估效率。
总结：图搜索中，“状态”的精确定义决定算法正确性。对于具有方向依赖行为的问题，必须将方向纳入状态空间，并辅以距离记忆化剪枝，才能让 DFS 可靠求解最短路径。
