1
# Runtime: 329 ms (Top 84.2%) | Memory: 17.67 MB (Top 84.2%)
2

3

4
class Solution:
5
    def shortestBridge(self, grid):
6
        m, n = len(grid), len(grid[0])
7
        start_i, start_j = next(
8
            (i, j) for i in range(m) for j in range(n) if grid[i][j]
9
        )
10

11
        stack = [(start_i, start_j)]
12
        visited = set(stack)
13
        while stack:
14
            i, j = stack.pop()
15
            visited.add((i, j))
16
            for ii, jj in (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j):
17
                if (
18
                    0 <= ii < m
19
                    and 0 <= jj < n
20
                    and grid[ii][jj]
21
                    and (ii, jj) not in visited
22
                ):
23
                    stack.append((ii, jj))
24
                    visited.add((ii, jj))
25

26
        ans = 0
27
        queue = list(visited)
28
        while queue:
29
            new_queue = []
30
            for i, j in queue:
31
                for ii, jj in (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j):
32
                    if 0 <= ii < m and 0 <= jj < n and (ii, jj) not in visited:
33
                        if grid[ii][jj] == 1:
34
                            return ans
35
                        new_queue.append((ii, jj))
36
                        visited.add((ii, jj))
37
            queue = new_queue
38
            ans += 1