Problem statement

https://binarysearch.com/problems/Nearest-Bus-Stop-From-a-House /

Solution

Usual multi-soruce bfs here.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, grid):
        N, M = len(grid), len(grid[0])
        neibs = [[-1,0],[0,-1],[0,1],[1,0]]
        queue = deque()
        for x in range(N):
            for y in range(M):
                if grid[x][y] == 2: queue.append((0, x, y))
        V = set()
        
        while queue:
            dist, x, y = queue.popleft()
            if grid[x][y] == 3: return dist
            for dx, dy in neibs:
                if 0<=x+dx<N and 0<=y+dy<M and grid[x+dx][y+dy] in [0, 3] and (x+dx, y+dy) not in V:
                    V.add((x+dx,y+dy))
                    queue.append((dist + 1, x+dx, y+dy))
                
        return -1