# Java Standard Dijkstra's algorithm with PriorityQueue

• ``````    private class point {
private int row, col, dist;
private String path;
point(int r, int c, int d, String p) {
row = r;
col = c;
dist = d;
path = p;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char[] turns = {'d', 'u', 'r', 'l'};
int m = maze.length, n = maze[0].length;
boolean[][] marked = new boolean[m][n];
PriorityQueue<point> minheap = new PriorityQueue<>(new Comparator<point>() {
@Override
public int compare(point o1, point o2) {
if (o1.dist == o2.dist) return o1.path.compareTo(o2.path);
else return o1.dist-o2.dist;
}
});
minheap.add(new point(ball[0], ball[1], 0, ""));
while (!minheap.isEmpty()) {
point cur = minheap.poll();
int row = cur.row, col = cur.col;
if (row == hole[0] && col == hole[1]) return cur.path;
if (marked[row][col]) continue;
marked[row][col] = true;
for (int i = 0; i < 4; i++) {
int r = row, c = col, dist = cur.dist;
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0 && (r != hole[0] || c != hole[1])) {
r += dirs[i][0];
c += dirs[i][1];
dist++;
}
if (r != hole[0] || c != hole[1]) {
r -= dirs[i][0];
c -= dirs[i][1];
dist--;
}
if (!marked[r][c]) {
minheap.add(new point(r, c, dist, cur.path+turns[i]));
}
}
}
return "impossible";
}
``````

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