This code finds a path through a binary matrix to a location with '9'.

Each iteration, dequeues a root and checks if all children are in bound and contain '0'. If so, that child is added to the queue.

Each que element 'Box' has a parent, which will give the path if followed once the target is reached.

The code gets stuck because the que somehow just increases in size and is never empty. Am I missing something?

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

CodePudding user response：

You'll need to keep a track of the visited nodes.

0,0 will queue 0,1, 0,1 will queue 0,0 again, and this will go on indefinitely. As soon as you pop the queue, mark the node as visited. While queueing neighbours for a root, don't enqueue the visited ones.