Today's Challenge

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

Shortest Path in Binary Matrix - LeetCode

offset을 tuple의 묶음으로 표시할 수 있는 걸 배움
나머지는 bfs의 연속인 듯. 일단 최소 비용을 1로 놓고 시작. (2 x 2 인 경우)

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]:
            return -1
        n = len(grid)
        
        offsets = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        qu = deque()
        qu.append((0, 0))
        visited = {(0, 0)}
        
        def get_adj(x, y):
            for x_offset, y_offset in offsets:
                nx = x + x_offset
                ny = y + y_offset
                
                if 0 <= nx < n and 0 <= ny < n and not grid[nx][ny] and (nx, ny) not in visited:
                    yield (nx, ny)
            
        cur = 1
        while qu:
            l = len(qu)
            
            for _ in range(l):
                r, c = qu.popleft()
                
                if r == n-1 and c == n-1:
                    return cur
                
                for p in get_adj(r, c):
                    visited.add(p)
                    qu.append(p)
                    
            cur += 1
        return -1