This is a standard BFS finding the path through a 2D array maze of 1s and 0s to find a 9.

when dequeue-ing, node coordinates are stored as a string to a hashMap. Items are only added to the queue if they are within bounds, contain a 0, or 9, and are not in the hashMap keys.

The loop exits without ever reaching the target. And I have no idea which part is wrong.

    public static Queue<Box> q = new LinkedList<Box>();
    public static HashMap<String,Boolean> map_seen = new HashMap<String,Boolean>();
    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();
            String ps = Integer.toString(p.x)   Integer.toString(p.y);
            map_seen.put(ps, true);

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

            if(isFree(maze, p.x 1,p.y)) {             
                Box nextP= new Box(p.x 1,p.y,p);
                String nextS= Integer.toString(p.x 1)   Integer.toString(p.y);
                if(!map_seen.containsKey(nextS)) {
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x-1,p.y)) {               
                Box nextP= new Box(p.x-1,p.y,p);
                String nextS= Integer.toString(p.x-1)   Integer.toString(p.y);
                if(!map_seen.containsKey(nextS)) {
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x,p.y 1)) {               
                Box nextP= new Box(p.x,p.y 1,p);
                String nextS= Integer.toString(p.x)   Integer.toString(p.y 1);
                if(!map_seen.containsKey(nextS)) {
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x,p.y-1)) {
                Box nextP= new Box(p.x,p.y-1,p);
                String nextS= Integer.toString(p.x)   Integer.toString(p.y-1);
                if(!map_seen.containsKey(nextS)) {
                    q.add(nextP);
                }
            }
        }
        System.out.println("exited reached");
    }


    public static boolean isFree(int[][] maze, int x, int y) {
        if((x >= 0 && x < maze[0].length) && (y >= 0 && y < maze.length) && (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：

I don't know if it is the only problem, but using

        String ps = Integer.toString(p.x)   Integer.toString(p.y);

as a key is definitely wrong. The boxes [1, 10] and [11, 0] produce the same string. It means that once you visit [1, 10], you will consider [11, 0] as visited, and never explore its paths. At least add a separator

        String ps = Integer.toString(p.x)   ":"   Integer.toString(p.y);

But why not use the boxes themselves as keys?

As a side note, map<whatever, bool> is a set on steroids. Just use a set.

CodePudding user response：

I think your code may be changed like this.

public static Queue<Box> q = new LinkedList<Box>();
    public static HashMap<String,Boolean> map_seen = new HashMap<String,Boolean>();
    public static void searchPath(int[][] maze, int x, int y, ArrayList<Integer> path) {
        auto b = new Box(x,y,null);
        q.add(b);
        map_seen.put(*b, true);

        while(!q.isEmpty()) {
            
            Box p = q.poll();
            String ps = Integer.toString(p.x)   Integer.toString(p.y);

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

            if(isFree(maze, p.x 1,p.y)) {             
                Box nextP= new Box(p.x 1,p.y,p);
                String nextS= Integer.toString(p.x 1)   Integer.toString(p.y);
                if(!map_seen.containsKey(nextS)) {
                    map_seen.put(nextS, true);
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x-1,p.y)) {               
                Box nextP= new Box(p.x-1,p.y,p);
                String nextS= Integer.toString(p.x-1)   Integer.toString(p.y);
                if(!map_seen.containsKey(nextS)) {
                    map_seen.put(nextS, true);
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x,p.y 1)) {               
                Box nextP= new Box(p.x,p.y 1,p);
                String nextS= Integer.toString(p.x)   Integer.toString(p.y 1);
                if(!map_seen.containsKey(nextS)) {
                    map_seen.put(nextS, true);
                    q.add(nextP);
                }
            }

            if(isFree(maze, p.x,p.y-1)) {
                Box nextP= new Box(p.x,p.y-1,p);
                String nextS= Integer.toString(p.x)   Integer.toString(p.y-1);
                if(!map_seen.containsKey(nextS)) {
                    map_seen.put(nextS, true);
                    q.add(nextP);
                }
            }
        }
        System.out.println("exited reached");
    }
}