基于BFS的矩阵迷宫寻路代码陷入循环问题排查

你的代码陷入无限循环、队列持续增大的核心原因是没有标记已访问过的节点，导致同一个格子被反复加入队列，永远处理不完。

问题细节拆解 #

你的逻辑里，每次只判断相邻节点是否在边界内、值为0/9/2，但：

• 你把已访问节点标记为2的操作是在找到终点后才执行的（getPath方法里），这时候队列里已经塞满了重复节点
• isFree方法还允许值为2的节点被加入队列，等于完全没做访问控制

比如从A走到B，之后B又能走回A，A再走回B，循环往复，队列只会越来越大。

修复方案 #

1. 节点加入队列前标记为已访问

在把节点加入队列时，立刻将其标记为已访问（设为2），这样后续判断时就不会再把它加入队列。

2. 调整isFree的判断条件

去掉允许maze[y][x]==2的逻辑，已访问的节点不能再被当作可通行节点。

3. 修正getPath里的重复标记逻辑

既然已经在入队时标记过，getPath里就不需要再重复标记，避免混淆。

修改后的代码示例 #

public static Queue<Box> q = new LinkedList<Box>();
public static void searchPath(int[][] maze, int x, int y, ArrayList<Integer> path) {
    q.add(new Box(x,y,null));
    // 起点先标记为已访问
    maze[y][x] = 2;

    while(!q.isEmpty()) {
        Box p = q.poll();

        if (maze[p.y][p.x] == 9) {
            System.out.println("Exit is reached!");
            getPath(p, path);
            return;
        }

        if(isFree(maze, p.x+1,p.y)) {             
            Box nextP= new Box(p.x+1,p.y,p);
            // 加入队列前标记为已访问，防止被其他路径重复加入
            maze[nextP.y][nextP.x] = 2;
            q.add(nextP);
        }

        if(isFree(maze, p.x-1,p.y)) {               
            Box nextP= new Box(p.x-1,p.y,p);
            maze[nextP.y][nextP.x] = 2;
            q.add(nextP);
        }

        if(isFree(maze, p.x,p.y+1)) {               
            Box nextP= new Box(p.x,p.y+1,p);
            maze[nextP.y][nextP.x] = 2;
            q.add(nextP);
        }

        if(isFree(maze, p.x,p.y-1)) {
            Box nextP= new Box(p.x,p.y-1,p);
            maze[nextP.y][nextP.x] = 2;
            q.add(nextP);
        }
    }
}

public static boolean isFree(int[][] maze, int x, int y) {
    // 只允许未访问的0和终点9
    if((x >= 0 && x < maze.length) && (y >= 0 && y < maze[x].length) && (maze[y][x] == 0 || maze[y][x] == 9)) {
        return true;
    }
    return false;
}

public static ArrayList<Integer> getPath(Box node, ArrayList<Integer> path){
    while(node!=null){
        path.add(node.x);
        path.add(node.y);
        node = node.parent;
    }
    return path;
}

额外说明 #

• 标记已访问的时机也可以是节点出队后，只要保证同一个节点不会被多次加入队列即可
• 如果不想修改原矩阵，可以单独维护一个visited二维数组记录访问状态，避免破坏原数据

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