JZX轻语：简

LeetCode 934 - 最短的桥

发表于2024年05月26日

#BFS

搜索题目，首先找到其中一个岛屿，并将其进行“染色”以便于和另一个岛屿区分 - 例如将其所有的元素都置为2，并记录下所有的边界元素。然后使用BFS搜索，将边界元素加入队列，不断扩展，直至找到另一个岛屿。第一个找到的岛屿的距离即为最短的桥长。

from collections import deque


class Solution:
    moves = ((-1, 0), (1, 0), (0, -1), (0, 1))

    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)

        def bfs(r: int, c: int) -> int:
            q = deque([(r, c)])
            bounding = set()
            while q:
                r, c = q.popleft()
                grid[r][c] = 2
                
                for move in self.moves:
                    nr, nc = r + move[0], c + move[1]

                    if nr < 0 or nr >= n or nc < 0 or nc >= n:
                        continue
                    if grid[nr][nc] == 0:
                        bounding.add((r, c, 0))
                        continue
                    if grid[nr][nc] == 1:
                        q.append((nr, nc))
            
            q = deque(bounding)
            visited = set()
            while q:
                r, c, dist = q.popleft()
                if grid[r][c] == 1:
                    return dist - 1
                
                for move in self.moves:
                    nr, nc = r + move[0], c + move[1]
                    if nr < 0 or nr >= n or nc < 0 or nc >= n or grid[nr][nc] == 2 or (nr, nc) in visited:
                        continue
                    visited.add((nr, nc))
                    q.append((nr, nc, dist + 1))
            return -1
                    
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    return bfs(i, j)
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/shortest-bridge/