934.最短的桥

最短的桥

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

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

你可以将 0 变为 1 ，从而将两座岛连接成一座岛。

返回实现两座桥接所需的最小翻转次数。

示例 1:

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

示例 2:

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

提示:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] 为 0 或 1
• grid 中恰好存在两座岛

解析

先用 DFS 标记其中一个岛屿，然后从该岛屿出发使用 BFS 找到到另一个岛屿的最短距离。

var shortestBridge = function (grid) {
  const n = grid.length;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let queue = [];

  const dfs = (i, j) => {
    if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== 1) return;
    grid[i][j] = 2;
    queue.push([i, j]);
    for (const [dx, dy] of dirs) dfs(i + dx, j + dy);
  };

  outer: for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j);
        break outer;
      }
    }
  }

  let step = 0;
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const [x, y] = queue.shift();
      for (const [dx, dy] of dirs) {
        const nx = x + dx, ny = y + dy;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (grid[nx][ny] === 2) continue;
        if (grid[nx][ny] === 1) return step + 1;
        grid[nx][ny] = 2;
        queue.push([nx, ny]);
      }
    }
    step++;
  }

  return -1;
};

时间复杂度 O(n²)，空间复杂度 O(n²)。