Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.4 kB
0
Indexable
Never
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid == null || grid.length == 0) return -1;
        if(grid[0][0] == 1) return -1;
        
        return traverse(grid);
        
    }
    
    public int traverse(int[][] grid){
        Queue<int[]> q = new LinkedList<>();
        // Set<String> visited = new HashSet<>();
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        q.add(new int[]{0, 0});
        int[] x = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
        int[] y = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
        int dist = 0;
        while(!q.isEmpty()){
            int size = q.size();
            dist++;
            for(int i = 0; i < size; i++){
                int[] coord = q.poll();
                if(coord[0] == grid.length -1 && coord[1] == grid[0].length - 1) return dist;
                // visited.add(Integer.toString(coord[0]) + "+" + Integer.toString(coord[1]));
                visited[coord[0]][coord[1]] = true;
                for(int idx = 0; idx < x.length; idx++){
                    int newX = coord[0] + x[idx];
                    int newY = coord[1] + y[idx];
                    if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length || grid[newX][newY] != 0 || visited[newX][newY]) continue;
                    q.add(new int[]{newX, newY});
                }
            }
        }
        
        return -1;
    }
}