> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/graphs/shortest-path-in-binary-matrix.md).

# Shortest Path in Binary Matrix

## Problem

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.

![](/files/-MRLXGQaccfVpVveXsfa)

![](/files/-MRLXO2XsG9OYVGesGnq)

### Thought Process

* Can traverse 8-directionally

* $$C\_1$$ is at (0, 0) and $$C\_k$$ is at (N-1, N-1) i.e. the last cell

* Return shortest path from top left to bottom right

## Solution

```
from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        visited = set()
        q = deque()
        q.append([0,0])
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
 
        grid[0][0] = 1
      
        
        direc = [[-1,0], [1,0],[0,-1], [0,1], [-1,-1], [-1,1],[1,-1],[1,1]]
        
        while q:
            coor = q.popleft()
            x = coor[0]
            y = coor[1]
            for i in direc:
                newX = x+i[0]
                newY = y+i[1]
                
                if newX < 0 or newX >= len(grid) or newY < 0 or newY >= len(grid[0]) or (newX, newY) in visited or grid[newX][newY] == 1:
                    continue
                    
                grid[newX][newY] = grid[x][y]+1
                visited.add((newX,newY))
                q.append([newX, newY])
                
        return grid[-1][-1] if grid[-1][-1] != 0 else -1
```

## Time Complexity

* **Time:** O(n) where n is the number of 0's in our queue since we're pulling them out and looking at the neighbors
* **Space:** O(n) where n is the number of 0's for the shortest path