LC934. Shortest Bridge

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        """tc O(R*C) sc O(R*C)
        1. mark one of island as 2
        2. dfs at each pos, spread 4 dirs, find each # island, push it to q
        3. bfs to iterate all coordinates in queue, check 4 directions, if they has reached #1 island
        if not, update distance, if yes return distance 
        """
        r = len(A)
        c = len(A[0])
        q = collections.deque()
        COLOR = 2 
        
        def neighbours(i,j):
            for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):  # for generator, need to use nestetd tuple instead of list (immutable)
                dx = i + di 
                dy = j + dj
                if 0 <= dx < r and 0<=dy< c:
                    yield dx,dy  # return generator 
        
        
        # color one island, put colored island into queue   
        def dfs(i,j):
            if A[i][j] == 1:
                q.append((i,j))
                A[i][j] = COLOR
                for ix,jy in neighbours(i,j):
                    if A[ix][jy] == 1:
                        dfs(ix,jy)
        # expand colored island, mark non-island area as colored .  expand until reach A[i][j] = 1 , another island found 
        # why here we can guaranteen shorted distance? since steps increase as each round we expend the island.
        def bfs():
            steps = 0
            while q:
                size = len(q)
                for _ in range(size):
                    x,y = q.popleft()
                    for xi,yj in neighbours(x,y):
                        if A[xi][yj] == 0:
                            A[xi][yj] = 2
                            q.append((xi,yj))
                        elif A[xi][yj] == 1:
                            return steps
                steps += 1
            return -1
        
        for i in range(r):
            for j in range(c):
                if A[i][j] == 1:
                    dfs(i,j)
                    return bfs()