0934. 最短的桥【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS + BFS

1. 📝 题目描述

• leetcode

给你一个大小为 n x n 的二元矩阵 grid，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛。

你可以将任意数量的 0 变为 1，以使两座岛连接起来，变成 一座岛。

返回必须翻转的 0 的最小数目。

---

示例 1：

输入：grid = [[0,1],[1,0]]
输出：1

示例 2：

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：grid = [
  [1, 1, 1, 1, 1],
  [1, 0, 0, 0, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 0, 0, 1],
  [1, 1, 1, 1, 1]
]

输出：1

---

提示：

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] 为 0 或 1
• grid 中恰有两个岛

2. 🎯 s.1 - DFS + BFS

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestBridge = function (grid) {
  const n = grid.length
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]
  const queue = []
  let found = false

  // DFS 标记第一个岛为 2
  const dfs = (i, j) => {
    grid[i][j] = 2
    queue.push([i, j])
    for (const [di, dj] of dirs) {
      const ni = i + di,
        nj = j + dj
      if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] === 1) {
        dfs(ni, nj)
      }
    }
  }

  for (let i = 0; i < n && !found; i++) {
    for (let j = 0; j < n && !found; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j)
        found = true
      }
    }
  }

  // BFS 找第二个岛
  let step = 0
  while (queue.length) {
    const size = queue.length
    for (let s = 0; s < size; s++) {
      const [x, y] = queue.shift()
      for (const [di, dj] of dirs) {
        const nx = x + di,
          ny = y + dj
        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
          if (grid[nx][ny] === 1) return step
          if (grid[nx][ny] === 0) {
            grid[nx][ny] = 2
            queue.push([nx, ny])
          }
        }
      }
    }
    step++
  }

  return -1
}

• 时间复杂度：$O(n^2)$，其中 n 是矩阵的边长
• 空间复杂度：$O(n^2)$，BFS 队列

算法思路：

• 用 DFS 标记第一个岛的所有格子为 2，并全部加入 BFS 队列
• 从队列做 BFS 向外扩展，每层扩展一步
• 当 BFS 遇到值为 1 的格子（第二个岛），返回当前步数即为最少翻转数