# Best first search + heuristic optimization

• 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<>();
while (!minHeap.isEmpty()) {
Node cur = minHeap.poll();
if (cur.distanceToDest == 0) {
return cur.step;
}
}
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;
}
}
}
}
``````

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