Shortest Path in Binary Matrix

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

• Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)

• C_1 is at location (0, 0) (ie. has value grid[0][0])

• C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])

• If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:

Input: [[0,1],[1,0]]
Output: 2

Example 2: Input: [[0,0,0],[1,1,0],[1,1,0]] Output: 4

Note:

1. 1 <= grid.length == grid[0].length <= 100

2. grid[r][c] is 0 or 1

Solution:

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
       int n = grid.length;
        int m = grid[0].length;
        if(grid[0][0]==1||grid[n-1][m-1]==1)return -1;
        if(n==1 && m==1 && grid[0][0]==0)return 1;
        int res=1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        
        int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1},
                                         {1,1},{1,-1},{-1,1},{-1,-1}};
        
        while(!q.isEmpty()){
            int qsize = q.size();
            for(int i=0;i<qsize;i++){
                int[] arr = q.poll();
                
                for(int j=0;j<8;j++){
                    int newx = arr[0]+directions[j][0];
                    int newy = arr[1]+directions[j][1];
                    
                    if(newx<0||newy<0||newx>=n||newy>=m||
                      grid[newx][newy]==1)continue;
                    if(newx==n-1 && newy==m-1) return res+1;
                    grid[newx][newy] = 1;
                    q.add(new int[]{newx,newy});
                }
            }
            res++;
        }
        
        return -1;
    }
}