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 lengthkif and only if it is composed of cellsC_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.

public class Solution {
    public int ShortestPathBinaryMatrix(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        if(grid[0][0] == 1 || grid[m-1][n-1] == 1){
            return -1;
        }
        bool[][] isVisited = new bool[m][];
        for(int i = 0; i < m ; i++){
            isVisited[i] = new bool[n];
        }

        Queue<int[]> q = new Queue<int[]>();

        q.Enqueue(new int[]{0, 0});
        isVisited[0][0] = true;

        int[][] dirs = new int[8][];

        dirs[0] = new int[]{-1, 0};
        dirs[1] = new int[]{1, 0};
        dirs[2] = new int[]{0, -1};
        dirs[3] = new int[]{0, 1};
        dirs[4] = new int[]{-1,-1};
        dirs[5] = new int[]{1,-1};
        dirs[6] = new int[]{-1, 1};
        dirs[7] = new int[]{1,1};

        int ans = 0;

        while(q.Count > 0){
            int size = q.Count;

            for(int l=0 ;l <size;l++) {

                var curr = q.Dequeue();

                if(curr[0] == m - 1 && curr[1] == n -1){
                    return ans + 1;
                }
                for(int i = 0; i < 8; i++){
                    int x = curr[0] + dirs[i][0];
                    int y = curr[1] + dirs[i][1];

                    if(x < 0 || x >= m || y < 0 || y >= m || isVisited[x][y] || grid[x][y] == 1){
                        continue;
                    }
                    q.Enqueue(new int[]{x, y});
                    isVisited[x][y] = true;
                }
            }
            ans ++; 
        }
        return -1;
    }
}