Shortest Path in Binary Matrix

BFS

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.

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