1091. Shortest Path in Binary Matrix

special shortest path where each path has equal weight

DIRECTIONS = [
    (-1, -1), (-1, 0), (-1, 1), 
    (0, -1), (0, 1), 
    (1, -1), (1, 0), (1, 1)
]

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        
        visited = set([(0, 0)])
        queue = collections.deque([(0, 0, 1)])
        while queue:
            row, col, dist = queue.popleft()
            if row == n - 1 and col == n - 1:
                return dist
            for dr, dc in DIRECTIONS:
                new_row = row + dr
                new_col = col + dc
                if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:
                    visited.add((new_row, new_col))
                    queue.append((new_row, new_col, dist+1))
        return -1

solution 2: iterate based on shortest path, can be extended to support case where weight is not equal

to find shortest path using bfs, should use popleft() instead of pop

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        
        direction = [
            (-1, -1), (-1, 0), (-1, 1), 
            (0, -1), (0, 1), 
            (1, -1), (1, 0), (1, 1)
        ]
        dist = [[-1 for _ in range(n)] for _ in range(n)]
        dist[0][0] = 1
        queue = collections.deque()
        queue.append((0, 0, dist[0][0]))
        while queue:
            x, y, d = queue.popleft()
            if x == n - 1 and y == n - 1:
                break
            for dx, dy in direction:
                new_x = x + dx
                new_y = y + dy
                if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 0 and (dist[new_x][new_y] == -1 or dist[new_x][new_y] > d + 1):
                    dist[new_x][new_y] = d + 1
                    queue.append((new_x, new_y, dist[new_x][new_y]))
        return dist[n-1][n-1]

1091. Shortest Path in Binary Matrix - cocoder39/coco39_LC GitHub Wiki