发表于 2024.05.26

• 搜索题目，首先找到其中一个岛屿，并将其进行“染色”以便于和另一个岛屿区分 - 例如将其所有的元素都置为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 题目链接