1091. Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix

可以先練習這些題目

• 200. Number of Islands
• 329. Longest Increasing Path in a Matrix

這個題目只是把 directions 複雜化了。

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        
        rows = len(grid) - 1
        cols = len(grid[0]) - 1

        if grid[0][0] != 0 or grid[rows][cols] != 0:
            return -1

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

        queue = deque()
        queue.append((0, 0))
        grid[0][0] = 1 
        
        while queue:
            row, col = queue.popleft()
            distance = grid[row][col]
            if (row, col) == (rows, cols):
                return distance

            neighbors = []
            for dx, dy in directions:
                x = row + dx
                y = col + dy
                if not(0 <= x <= rows and 0 <= y <= cols):
                    continue
                if grid[x][y] != 0:
                    continue
                neighbors.append((x, y))
            
            for x, y in neighbors:
                grid[x][y] = distance + 1
                queue.append((x, y))
            
        return -1