Question

934. 最短的桥

English Version

题目描述

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

解法

方法一：DFS + BFS

题目求解的是最小翻转次数，使得两个岛屿相连，实际上等价于求解两个岛屿之间的最短距离。

因此，我们可以先通过 DFS 将其中一个岛屿的所有点找出来，放到一个队列 $q$ 中。然后通过 BFS 一层层向外扩展，直至碰到另一个岛屿，此时将当前扩展的层数作为答案返回即可。

在 DFS 和 BFS 搜索的过程中，我们直接将已经访问过的点标记为 $2$，这样就不会重复访问。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为矩阵的行数或列数。

class Solution:
  def shortestBridge(self, grid: List[List[int]]) -> int:
    def dfs(i, j):
      q.append((i, j))
      grid[i][j] = 2
      for a, b in pairwise(dirs):
        x, y = i + a, j + b
        if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
          dfs(x, y)

    n = len(grid)
    dirs = (-1, 0, 1, 0, -1)
    q = deque()
    i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
    dfs(i, j)
    ans = 0
    while 1:
      for _ in range(len(q)):
        i, j = q.popleft()
        for a, b in pairwise(dirs):
          x, y = i + a, j + b
          if 0 <= x < n and 0 <= y < n:
            if grid[x][y] == 1:
              return ans
            if grid[x][y] == 0:
              grid[x][y] = 2
              q.append((x, y))
      ans += 1

class Solution {
  private int[] dirs = {-1, 0, 1, 0, -1};
  private Deque<int[]> q = new ArrayDeque<>();
  private int[][] grid;
  private int n;

  public int shortestBridge(int[][] grid) {
    this.grid = grid;
    n = grid.length;
    for (int i = 0, x = 1; i < n && x == 1; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          dfs(i, j);
          x = 0;
          break;
        }
      }
    }
    int ans = 0;
    while (true) {
      for (int i = q.size(); i > 0; --i) {
        var p = q.pollFirst();
        for (int k = 0; k < 4; ++k) {
          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n) {
            if (grid[x][y] == 1) {
              return ans;
            }
            if (grid[x][y] == 0) {
              grid[x][y] = 2;
              q.offer(new int[] {x, y});
            }
          }
        }
      }
      ++ans;
    }
  }

  private void dfs(int i, int j) {
    grid[i][j] = 2;
    q.offer(new int[] {i, j});
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y);
      }
    }
  }
}

class Solution {
public:
  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};

  int shortestBridge(vector<vector<int>>& grid) {
    int n = grid.size();
    queue<pair<int, int>> q;
    function<void(int, int)> dfs = [&](int i, int j) {
      grid[i][j] = 2;
      q.emplace(i, j);
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
          dfs(x, y);
        }
      }
    };
    for (int i = 0, x = 1; i < n && x; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          dfs(i, j);
          x = 0;
          break;
        }
      }
    }
    int ans = 0;
    while (1) {
      for (int h = q.size(); h; --h) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n) {
            if (grid[x][y] == 1) return ans;
            if (grid[x][y] == 0) {
              grid[x][y] = 2;
              q.emplace(x, y);
            }
          }
        }
      }
      ++ans;
    }
  }
};

func shortestBridge(grid [][]int) (ans int) {
  n := len(grid)
  dirs := []int{-1, 0, 1, 0, -1}
  type pair struct{ i, j int }
  q := []pair{}
  var dfs func(int, int)
  dfs = func(i, j int) {
    grid[i][j] = 2
    q = append(q, pair{i, j})
    for k := 0; k < 4; k++ {
      x, y := i+dirs[k], j+dirs[k+1]
      if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 {
        dfs(x, y)
      }
    }
  }
  for i, x := 0, 1; i < n && x == 1; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == 1 {
        dfs(i, j)
        x = 0
        break
      }
    }
  }
  for {
    for i := len(q); i > 0; i-- {
      p := q[0]
      q = q[1:]
      for k := 0; k < 4; k++ {
        x, y := p.i+dirs[k], p.j+dirs[k+1]
        if x >= 0 && x < n && y >= 0 && y < n {
          if grid[x][y] == 1 {
            return
          }
          if grid[x][y] == 0 {
            grid[x][y] = 2
            q = append(q, pair{x, y})
          }
        }
      }
    }
    ans++
  }
}