Java BFS with Some optimizations, 19 ms (with comments)


  • 6

    The idea is similar to the Dijkstra's shortest Path Algorithm.

    public class Solution {
        private int[][] maze;
        private int[][] minSteps;//memorize the minimus steps to reach each position
        private int[][] dirs={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            this.maze=maze;
            this.minSteps=new int[maze.length][maze[0].length];
            /*Initiallize minSteps matrix*/
            for(int i=0; i<maze.length; i++){
                for(int j=0; j<maze[0].length; j++){
                    minSteps[i][j]=Integer.MAX_VALUE;
                }
            }
            /*Optimization: check if the destination is impossible to Reach*/
            boolean desL=canRoll(destination[0], destination[1], dirs[0]);
            boolean desR=canRoll(destination[0], destination[1], dirs[1]);
            boolean desD=canRoll(destination[0], destination[1], dirs[2]);
            boolean desU=canRoll(destination[0], destination[1], dirs[3]);
            if(desL && desR && desD && desU) return -1; //all neighbors are walls
            else if(!(desL||desR||desD||desU)) return -1; //all neighbors are empty spaces
            else if(desL && desR && !desU && !desD) return -1; //two opposite neigbhors are walls, and the other two are empty spaces
            else if(!desL && !desR && desU && desD) return -1;//two opposite neigbhors are walls, and the other two are empty spaces
            
            minSteps[start[0]][start[1]]=0;
            /*BFS; Optimization: use PriorityQueue based on the steps instead of Queue*/
            PriorityQueue<Position> pq=new PriorityQueue<>();
            pq.offer(new Position(start[0], start[1], 0));
            while(!pq.isEmpty()){
                Position pos=pq.poll();
                /*optimization: if the destination is at the head of the queue, we are done*/
                if(pos.r==destination[0] && pos.c==destination[1]) return pos.steps;
                for(int[] dir: dirs){
                    int r=pos.r, c=pos.c, currSteps=0;
                    while(canRoll(r, c, dir)){
                        r+=dir[0];
                        c+=dir[1];
                        currSteps++;
                    }
                    int totalSteps=pos.steps+currSteps;
                    if(totalSteps<minSteps[r][c] && totalSteps<minSteps[destination[0]][destination[1]]){
                        minSteps[r][c]=totalSteps;
                        pq.offer(new Position(r, c, totalSteps));
                    }
                }
            }
            /*May not be able to reach the destination*/
            return minSteps[destination[0]][destination[1]]==Integer.MAX_VALUE? -1: minSteps[destination[0]][destination[1]];
        }
        
        private boolean canRoll(int r, int c, int[] dir){
            r+=dir[0];
            c+=dir[1];
            if(r<0 || c<0 || r>=maze.length || c>=maze[0].length || maze[r][c]==1) return false;
            return true;
        }
    }
    
    class Position implements Comparable<Position>{
        public int r;
        public int c;
        public int steps;
        
        public Position(int r, int c, int s){
            this.r=r;
            this.c=c;
            this.steps=s;
        }
        @Override
        public int compareTo(Position other){
            return this.steps-other.steps;
        }
    }
    

Log in to reply
 

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