Problem statement

https://binarysearch.com/problems/Shortest-Bridge/

Solution

Equal to Leetcode 0934. Shortest Bridge.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def shortestBridge(self, grid):
        m, n, num = len(grid), len(grid[0]), 2
        comps = defaultdict(list)
        
        def dfs(i, j, k):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != 1:
                return
            grid[i][j] = k
            comps[k] += [(i, j)]
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                dfs(x, y, k)

        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                dfs(i, j, num)
                num += 1

        V = set()
        q = deque([(-1, x, y) for x, y in comps[2]])
        while q:
            dist, i, j = q.popleft()
            if grid[i][j] == 3: return dist
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                if not 0 <= x < m or not 0 <= y < n or grid[x][y] == 2 or (x, y) in V: continue
                V.add((x, y))
                q += [(dist + 1, x, y)]