clean java bfs solution


  • 1
    G
    class point{
        int y;
        int x;
        int step;
        point(int y, int x, int step){
            this.y = y;
            this.x = x;
            this.step = step;
        }
    }
    
    public class Solution {
        
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int h = maze.length;
            int w = maze[0].length;
            int[][] matrix = new int[h+2][w+2];
            int[][] distances = new int[h+2][w+2];
            
            
            for(int i=0;i<h+2;i++){
                for(int j=0;j<w+2;j++){
                    matrix[i][j]=1;
                    
                }
            }
            
            for(int i=1;i<h+1;i++){
                for(int j=1;j<w+1;j++){
                    matrix[i][j]=maze[i-1][j-1];
                    distances[i][j]=99999;
                }
            }
            int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};
            Queue<point> qq = new LinkedList<point>();
            
            qq.add(new point(start[0]+1, start[1]+1, 0));
            
            while(!qq.isEmpty()){
                point temp = qq.poll();
    
                if(temp.step >= distances[temp.y][temp.x]){
                    continue;
                }
                
                distances[temp.y][temp.x]=temp.step;
                
                for(int[]dir:dirs){
                    int tpy = temp.y;
                    int tpx = temp.x;
                    int tpcurstep = temp.step;
                    while(matrix[tpy+dir[0]][tpx+dir[1]]!=1){
                        tpy +=dir[0];
                        tpx +=dir[1];
                        tpcurstep++;
                    }
                    qq.add(new point(tpy,tpx,tpcurstep));
                    
                }
                
            }
            return distances[destination[0]+1][destination[1]+1]==99999?-1:distances[destination[0]+1][destination[1]+1];
        }
    }

Log in to reply
 

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