DIRS = [1,0], [-1,0], [0,1], [0,-1], [-1,-1], [1,1], [1,-1], [-1,1](/ALawliet/algorithms/wiki/1,0],-[-1,0],-[0,1],-[0,-1],-[-1,-1],-[1,1],-[1,-1],-[-1,1)
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
ROWS = COLS = len(grid)
if grid[0][0] or grid[ROWS-1][COLS-1]:
return -1
Q = deque([ (0,0,1) ]) # (r, c, dist)
visited = set( (0,0) ) # (r, c)
while Q:
r, c, dist = Q.popleft()
if r == ROWS - 1 and c == COLS - 1:
return dist
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS:
if (nr, nc) not in visited and grid[nr][nc] == 0:
Q.append( (nr, nc, dist + 1) )
visited.add( (nr, nc) )
return -1