Best first search + heuristic optimization


  • -1
    B

    Re: [Java BFS with Some optimizations](19 ms (with comments))

    Based on Java BFS with Some optimizations, I optimized the compare function.

    public class Solution {
        class Node implements Comparable<Node> {
            int row;
            int col;
            int step;
            int distanceToDest;
            Node (int r, int c, int s, int[] destination) {
                row = r;
                col = c;
                step = s;
                distanceToDest = Math.abs(r - destination[0]) + Math.abs(c - destination[1]);
            }
            
            // heuristic optimization
            @Override
            public int compareTo(Node another) {
                if (step + distanceToDest == another.step + another.distanceToDest) {
                    return 0;
                }
                return step + distanceToDest > another.step + another.distanceToDest ? 1 : -1;
            }
        }
        
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int rowL = maze.length;
            int colL = maze[0].length;
            int[][] expanded = new int[rowL][colL];
            for (int i = 0; i < rowL; i++) {
                for (int j = 0; j < colL; j++) {
                    expanded[i][j] = Integer.MAX_VALUE;
                }
            }
            
            expanded[start[0]][start[1]] = 0;
            PriorityQueue<Node> minHeap = new PriorityQueue<>();
            minHeap.add(new Node(start[0], start[1], 0, destination));
            while (!minHeap.isEmpty()) {
                Node cur = minHeap.poll();
                if (cur.distanceToDest == 0) {
                    return cur.step;
                }
                addNext(maze, cur, destination, minHeap, expanded);
            }
            return -1;
        }
        
        private void addNext(int[][] maze, Node cur, int[] destination, PriorityQueue<Node> minHeap, int[][] expanded) {
            int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (int[] direction: directions) {
                int step = -1;
                int nextR = cur.row;
                int nextC = cur.col;
                
                do {
                    step++;
                    nextR += direction[0];
                    nextC += direction[1];
                } while (nextR >= 0 && nextR < maze.length && nextC >= 0 && nextC < maze[0].length && maze[nextR][nextC] == 0);
                
                // the maze[nextR][nextC] is wall, so we need roll back one step
                nextR -= direction[0];
                nextC -= direction[1];
                int totalStep = cur.step + step;
                
                // important pruning
                if (expanded[nextR][nextC] > totalStep) {
                    expanded[nextR][nextC] = totalStep;
                    minHeap.add(new Node(nextR, nextC, totalStep, destination));
                }
            }
        }
    }
    

Log in to reply
 

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