> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/dynamic-programming-i/shortest-path-in-binary-matrix.md).

# 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.

```
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;
    }
}
```