Short,clean and straight forward BFS solution with PriorityQueue


  • 4

    The idea is just using BFS with a PriorityQueue(dijkstra's algorithm), PriorityQueue polls out the Coordinate with the minimum distance, if there are two with same distance, we compare their lexicographical order, by this way, we can ensure that we get the lexicographically smallest way in the end.

    public class Solution {
        class Coordinate implements Comparable<Coordinate> {
            int x, y, dist;
            String moves;
    
            public Coordinate(int x, int y, int dist, String moves) {
                this.x = x;
                this.y = y;
                this.dist = dist;
                this.moves = moves;
            }
            
            public int compareTo(Coordinate that) {
                if (this.dist != that.dist)     return this.dist - that.dist;
                return this.moves.compareTo(that.moves);
            }
        }
        
        int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        char[] dirc = {'d', 'l', 'r', 'u'};
        
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
    
            boolean[][] visited = new boolean[m][n];
            
            PriorityQueue<Coordinate> pq = new PriorityQueue<>();
            pq.add(new Coordinate(ball[0], ball[1], 0, ""));
            
            while(!pq.isEmpty()) {
                Coordinate curr = pq.poll();
                
                if (curr.x == hole[0] && curr.y == hole[1]) {
                    return curr.moves;
                }
                
                if (!visited[curr.x][curr.y]) {
                    visited[curr.x][curr.y] = true;
                    for (int direction = 0; direction < 4; direction++) {
                        Coordinate next = moveForward(maze, curr, direction, hole);
                        pq.add(new Coordinate(next.x, next.y, next.dist, next.moves + dirc[direction]));
                    }
                }
            }
            return "impossible";
        }
        
    /*
        Start from current position move forward in one direction until hit the wall, return the last position before hitting the wall
    */
        private Coordinate moveForward(int[][] maze, Coordinate curr, int direction, int[] hole) {
            int m = maze.length, n = maze[0].length;
            int nx = curr.x, ny = curr.y, dis = curr.dist;
            while (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0) {
                nx += dirs[direction][0];
                ny += dirs[direction][1];
                dis++;
                if (nx == hole[0] && ny == hole[1]) {
                    return new Coordinate(nx, ny, dis, curr.moves);
                }
            }
            // back up one step from wall
            nx -= dirs[direction][0];
            ny -= dirs[direction][1];
            dis--;
            return new Coordinate(nx, ny, dis, curr.moves);
        }
    }
    

Log in to reply
 

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