中等

问题描述

给你一个大小为 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 中恰有两个岛

深度优先搜索 + 广度优先搜素

首先遍历矩阵，从遇到的第一个 $1$ 开始，进行一次深度优先搜索，对其中一座岛进行标记，然后从这座岛的坐标开始，进行一次广度优先搜索，当首次遇到另一座岛的坐标时，所遍历的层数即为最少步数。

/**
 * @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 = []
  const dfs = (x, y, color) => {
    grid[x][y] = color
    queue.push([x, y])
    for (const dir of dirs) {
      const xx = x + dir[0]
      const yy = y + dir[1]
      if (-1 < xx && xx < n && -1 < yy && yy < n) {
        if (grid[xx][yy] === 1) dfs(xx, yy, color)
      }
    }
  }
  label: for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j, -1)
        break label
      }
    }
  }
  let step = 0
  while (queue.length) {
    const length = queue.length
    for (let i = 0; i < length; i++) {
      const [x, y] = queue.shift()
      for (const dir of dirs) {
        const xx = x + dir[0]
        const yy = y + dir[1]
        if (-1 < xx && xx < n && -1 < yy && yy < n) {
          if (grid[xx][yy] === 1) {
            return step
          } else if (grid[xx][yy] === 0) {
            grid[xx][yy] = -1
            queue.push([xx, yy])
          }
        }
      }
    }
    step++
  }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$