Java Standard Dijkstra's algorithm with PriorityQueue


  • 0
        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";
        }
    

Log in to reply
 

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