java - BFS 通过矩阵迷宫陷入循环

Question

此代码查找通过二进制矩阵到包含“9”的位置的路径。

每次迭代，都会将根出列并检查所有子项是否都已绑定(bind)并包含“0”。如果是，则将该子级添加到队列中。

每个 que 元素“Box”都有一个父元素，一旦达到目标，它将给出路径。

代码被卡住了，因为队列的大小以某种方式增加并且永远不会为空。我错过了什么吗？

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));

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

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

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

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

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

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


    public static boolean isFree(int[][] maze, int x, int y) {
        if((x >= 0 && x < maze.length) && (y >= 0 && y < maze[x].length) && (maze[y][x] == 2 || maze[y][x] == 0 || maze[y][x] == 9)) {
            return true;
        }
        return false;
        
            
    }

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

Answer 1

您需要跟踪访问过的节点。

0,0 将排队 0,1，0,1 将再次排队 0,0，这将无限期地持续下去。一旦弹出队列，就将该节点标记为已访问。在将邻居排队等待根时，不要将已访问的邻居排队。