Java A* search (15ms)


  • 0

    This is a typical A* search problem.
    To insure the lexicographical order, when choosing the next state, we have to follow the order of "d","l","r","u" if the next possible stages have the same steps. Therefore, we also have to record the path for keeping the order as well as for output.

    public class Solution {
        int[][] dirs = new int[][]{{1,0},{0,-1},{0,1},{-1,0}};
        String[] dirsStr = new String[]{"d","l","r","u"};
        boolean[][] visited = new boolean[30][30];
        class Node {
            int i,j, steps;
            String path = "";
            Node(int i, int j, int steps, String path){
                this.i=i;
                this.j=j;
                this.steps=steps;
                this.path = path;
            }
            Node moveTo(int[][] maze, int d, int[] hole){
                int[] dir = dirs[d];
                int nextI = this.i, nextJ=this.j, nextSteps = 0;
                while (nextI+dir[0] >=0 && nextJ+dir[1] >=0  && nextI+dir[0] <maze.length &&
                    nextJ+dir[1] < maze[0].length && maze[nextI+dir[0]][nextJ+dir[1]] == 0) {
                    nextI+=dir[0];
                    nextJ+=dir[1];
                    nextSteps++;
                    if (nextI == hole[0] && nextJ==hole[1]) break;//reach the hole
                }
                return nextSteps == 0? null : new Node(nextI, nextJ, this.steps+nextSteps, this.path+dirsStr[d]); 
            }
        }
        class NodeComp implements Comparator<Node> {
            public int compare(Node n1, Node n2) {
                if (n1.steps == n2.steps) return n1.path.compareTo(n2.path);
                return n1.steps - n2.steps;
            }
        }
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            PriorityQueue<Node> queue = new PriorityQueue<>( new NodeComp() );
            queue.offer(new Node(ball[0], ball[1], 0, ""));
            while (! queue.isEmpty() ) {
                Node cur = queue.poll();
                visited[cur.i][cur.j] = true;
                if (cur.i == hole[0] && cur.j==hole[1]) return cur.path; 
                for (int i=0; i<4; i++) {
                    Node next = cur.moveTo(maze, i, hole);
                    if (next != null && ! visited[next.i][next.j]) queue.offer(next);
                }
            }
            return "impossible";
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.