[Leetcode] 1091. Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

initial

typical bfs graph prob but be careful to mark cur_cost as 1 when starting (its not 0). And we can only traverse grid that is value 0 so need to check that for next_x, and next_y

sol

from collections import deque
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        queue = deque()
        row,col = len(grid),len(grid[0])
        visited = [[False for _ in range(col)] for _ in range(row)]
        moves=[[1,1],[-1,-1],[1,-1],[-1,1],[0,1],[1,0],[-1,0],[0,-1]]
        if grid[0][0]!=0:
            return -1
        queue.append((0,0,1))
        visited[0][0]=True
        while queue:
            cur_x,cur_y,cur_cost=queue.popleft()
            if cur_x==row-1 and cur_y==col-1:
                return cur_cost
            for move in moves:
                next_x,next_y=move[0]+cur_x,move[1]+cur_y
                if 0<=next_x<row and 0<=next_y<col and not visited[next_x][next_y] and grid[next_x][next_y]==0:
                    visited[next_x][next_y]=True
                    queue.append((next_x,next_y,cur_cost+1))
        return -1

complexity

N^2 time and space