DFS求解LeetCode迷宫II问题时最短路径计算错误原因排查

迷宫中有一个小球，空地用0表示，墙壁用1表示。小球可以向上下左右四个方向滚动，但只有碰到墙壁时才会停止，停止后可选择下一个方向。给定m×n的迷宫、小球起始位置和目标位置，返回小球停在目标位置的最短距离，若无法到达则返回-1。距离定义为从起始位置（不含）到目标位置（含）经过的空地数量。

我用DFS实现了一个解法，想通过深度优先探索路径并记录步数来找到最短路径，但测试时发现结果不对——比如给定示例中正确最短路径是12，我的代码返回16。我知道BFS能求最短路径，但暂时想先搞懂DFS哪里错了。

我的代码如下：

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) {
        int[][] maze = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
        int[] start = {0,4};
        int[] destination = {4,4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE? -1 : shortest;
        
    }
    
    private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][]visited, int count) {
        if( visited[i][j]) {
            return;
        }
        if (i == destination[0] && j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }
        
        visited[i][j] = true;

        for (int[] dir : dirs) {
            int x = i;
            int y  = j;
            int 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++;
            }
            dfs(maze, x , y, destination, visited, newcount);
        }
    }
}

你的DFS代码核心问题 #

1. visited标记逻辑错误：你在进入某个停止点（i,j）时就标记为已访问，但实际上，可能存在一条更短的路径到达这个停止点，只是这条路径被你提前标记为已访问而无法继续探索。比如，第一次到达某个点时步数是10，但后来有一条步数为8的路径也能到这里，此时因为已经标记为visited，这条更优的路径就被跳过了，导致后续基于这个点的路径无法找到更短的总距离。

2. 缺少回溯逻辑：DFS的核心是回溯，但你的代码在标记visited[i][j] = true后，没有在递归结束后将其改回false。这会导致一旦某个点被访问过，后续所有可能的路径都无法再经过它，哪怕这条路径能得到更短的总步数。

修正方案 #

我们需要把visited改成记录到达每个停止点的最短步数，而不是简单的布尔值。这样，当再次到达同一个点时，如果当前步数比已记录的步数更少，才继续递归探索；否则直接跳过。

修正后的代码：

public class MazeII {
    int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) {
        int[][] maze = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
        int[] start = {0,4};
        int[] destination = {4,4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        // 用dist数组记录到达每个点的最短步数，初始化为无穷大
        int[][] dist = new int[maze.length][maze[0].length];
        for (int[] row : dist) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[start[0]][start[1]] = 0;
        dfs(maze, start[0], start[1], destination, dist);
        return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dist[destination[0]][destination[1]];
    }
    
    private void dfs(int[][] maze, int i, int j, int[] destination, int[][] dist) {
        for (int[] dir : dirs) {
            int x = i;
            int y = j;
            int count = dist[i][j];
            // 一直滚动直到碰到墙壁
            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];
                count++;
            }
            // 如果当前路径到达(x,y)的步数比已记录的更短，才继续探索
            if (count < dist[x][y]) {
                dist[x][y] = count;
                dfs(maze, x, y, destination, dist);
            }
        }
    }
}

修正说明 #

• 用dist数组替代visited，记录每个停止点的最短到达步数，初始值设为无穷大，起始点步数设为0。
• 每次滚动到新的停止点(x,y)时，只有当当前步数count小于dist[x][y]时，才更新并继续递归——这保证了我们只会探索更优的路径，不会重复走更长的路径。
• 去掉了全局变量shortest，直接通过dist数组获取目标点的最短步数，逻辑更清晰。

内容的提问来源于stack exchange，提问作者Spindoctor