0934 Shortest Bridge

0934 Shortest Bridge.py

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        r, c = len(A), len(A[0])
        start = set()
        dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]
        
        def dfs(i, j):
            A[i][j] = 2
            for d in dirs:
                x, y = i + d[0], j + d[1]
                if 0 <= x < r and 0 <= y < c:
                    if A[x][y] == 1:
                        dfs(x, y)
                    if A[x][y] == 0:
                        start.add((i, j))
                        
        def set_l1():
            for i in range(r):
                for j in range(c):
                    if A[i][j] == 1:
                        return dfs(i, j)
                    
        set_l1()
        from collections import deque
        step = 0
        q = deque(start)
        
        
        while q:
            l = len(q)
            for _ in range(l):
                i, j = q.popleft()
                for d in dirs:
                    x, y = i + d[0], j + d[1]
                    if 0 <= x < r and 0 <= y < c:
                        if A[x][y] == 1:
                            return step
                        elif A[x][y] == 0:
                            A[x][y] = -1
                            q.append((x, y))
            step += 1