Leetcode 971 Solution

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        m = len(A)
        n = len(A[0])

        i = 0
        j = 0

        for i, j in itertools.product(range(m), range(n)):
            if A[i][j] == 1:
                break

        q = []
        q.append((i, j))
        A[i][j] = 2

        while q:
            i, j = q.pop(0)

            if i > 0 and A[i - 1][j] == 1:
                A[i - 1][j] = 2
                q.append((i - 1, j))

            if i < m - 1 and A[i + 1][j] == 1:
                A[i + 1][j] = 2
                q.append((i + 1, j))

            if j > 0 and A[i][j - 1] == 1:
                A[i][j - 1] = 2
                q.append((i, j - 1))

            if j < n - 1 and A[i][j + 1] == 1:
                A[i][j + 1] = 2
                q.append((i, j + 1))

        q = []
        seen = set()
        for i in range(m):
            for j in range(n):
                if A[i][j] == 2:
                    q.append((i, j))
                    seen.add((i, j))

        step = 0
        while q:
            s = len(q)

            for _ in range(s):
                i, j = q.pop(0)

                if A[i][j] == 1:
                    return step - 1

                if i > 0 and (i - 1, j) not in seen:
                    seen.add((i - 1, j))
                    q.append((i - 1, j))

                if i < m - 1 and (i + 1, j) not in seen:
                    seen.add((i + 1, j))
                    q.append((i + 1, j))

                if j > 0 and (i, j - 1) not in seen:
                    seen.add((i, j - 1))
                    q.append((i, j - 1))

                if j < n - 1 and (i, j + 1) not in seen:
                    seen.add((i, j + 1))
                    q.append((i, j + 1))

            step += 1