934. 最短的桥（Rating 1825）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

934. 最短的桥

Rating 1825

思路

两次bfs

第一次bfs，找到1个岛所有的1

第二次bfs，基于第一个岛的边缘外扩，找到第一个不在第一个岛的1

代码

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        dir = [-1, 0, 1, 0, -1]
        m, n = len(grid), len(grid[0])
        
        dq = deque()
        vis = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dq.append((i, j))
                    vis.add((i, j))
                    break
            if dq:
                break
        edge = deque()
        vis_edge = set()
        while dq: # 第一次bfs
            i, j = dq.popleft()
            flag_is_edge = 0
            for d in range(4):
                nxi = i + dir[d]
                nxj = j + dir[d + 1]
                if nxi < 0 or nxi >= m or nxj < 0 or nxj >= n:
                    continue
                if (nxi, nxj) in vis:
                    continue
                if grid[nxi][nxj] == 1:
                    dq.append((nxi, nxj))
                    vis.add((nxi, nxj)) # 记录访问过的1，也就记录了第一个岛所有的1
                else: # 如果这个位置周边有0，表明这个位置是岛的边界
                    flag_is_edge = 1
            if flag_is_edge:
                edge.append((i, j))
                vis_edge.add((i, j))
        ret = 0
        while edge: # 第二次bfs，从第一个岛的边界开始外扩
            sz = len(edge)
            while sz:
                sz -= 1
                i, j = edge.popleft()
                for d in range(4):
                    nxi = i + dir[d]
                    nxj = j + dir[d + 1]
                    if nxi < 0 or nxi >= m or nxj < 0 or nxj >= n:
                        continue
                    if (nxi, nxj) in vis_edge:
                        continue
                    if grid[nxi][nxj] == 1 and (nxi, nxj) not in vis: # 找到第一个不在第一个岛的1
                        return ret
                    if grid[nxi][nxj] == 0:
                        edge.append((nxi, nxj))
                        vis_edge.add((nxi, nxj))
            ret += 1
        return -1