这篇文章希望和你深入探讨：为什么在 Maze II 这类滚动球问题里，直接用普通 DFS 寻找最短路径总是失败，以及如何通过两个关键的改进来“抢救”——答案在于：基于方向状态的三维 visited 标记，以及带距离剪枝的动态更新机制。
在图论与算法实践中，开发者误用 DFS 求解最短路径的情况并不罕见。尤其是 LeetCode 上的 Maze II 这类“滚动球”题目，要求球从起点出发，沿四个方向之一持续滚动直到撞墙才停，每个停下的点构成一个有效状态。最终目标是找到抵达终点的最短滚动距离，也就是经过的空格总数。
理论上，BFS 在无权图中是最短路径的天然解法，但不少开发人员却执着于用 DFS 实现，结果往往碰壁：示例输入理应为 12，裸 DFS 却返回 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）被视为两个独立状态，互不干扰。这样一来，所有合法路径分支都能被探索到，状态覆盖问题自然得到解决。
改进方案二：距离驱动剪枝 —— 动态更新最优代价
当然，仅区分方向还不够。更进一步的做法是：不仅要记录“是否来过”，还要记录“以某个方向到达某点时的最小步数”。将 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 并不适用。DFS 的改进版更有价值的地方在于：帮助你深刻理解状态建模的思想。
最终，一个正确实现的 DFS 不再是盲目的遍历，而是以状态空间建模为地基、以距离优化为引擎的精确搜索——这正是图算法从“能跑通”迈向“可证明正确”的关键一步。
