题目形容
这是 LeetCode 上的 934. 最短的桥 ，难度为 中等。
Tag : 「并查集」、「双向 BFS」
给你一个大小为 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或1grid中恰有两个岛
并查集 + 双向 BFS
应用「并查集」将两个岛标记进去，而后将两个岛的点别离入队，再使用「双向 BFS」来找最短通路。
为了不便，咱们将 grid 记为 g。
对于所有满足 $g[i][j] = 1$ 的节点与其四联通的方向，值同为 $1$ 的节点进行并查集连通性保护。
随后建设两个队列 d1 和 d2 别离存储两个岛的节点（以二元组 $(x, y)$ 的形式出入队），并应用两个哈希表 m1 和 m2 来记录从两岛屿登程达到该节点所耗费的步数（以节点的一维编号为 key，以耗费步数为 value）。
最初是应用「双向 BFS」来求解使两岛屿联通的最小通路：每次从队列中较少的进行拓展，只有尚未被解决过的节点（没有被以后哈希表所记录）才进行入队并更新耗费步数，当拓展节点在另外一个队列对应的哈希表表中呈现过，阐明找到了最短通路。
Java 代码：
class Solution { static int N = 10010; static int[] p = new int[N]; static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; int n; int getIdx(int x, int y) { return x * n + y; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void union(int x, int y) { p[find(x)] = p[find(y)]; } public int shortestBridge(int[][] g) { n = g.length; for (int i = 0; i <= n * n; i++) p[i] = i; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == 0) continue; for (int[] di : dirs) { int x = i + di[0], y = j + di[1]; if (x < 0 || x >= n || y < 0 || y >= n) continue; if (g[x][y] == 0) continue; union(getIdx(i, j), getIdx(x, y)); } } } int a = -1, b = -1; Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>(); Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == 0) continue; int idx = getIdx(i, j), root = find(idx); if (a == -1) a = root; else if (a != root && b == -1) b = root; if (root == a) { d1.addLast(new int[]{i, j}); m1.put(idx, 0); } else if (root == b) { d2.addLast(new int[]{i, j}); m2.put(idx, 0); } } } while (!d1.isEmpty() && !d2.isEmpty()) { int t = -1; if (d1.size() < d2.size()) t = update(d1, m1, m2); else t = update(d2, m2, m1); if (t != -1) return t - 1; } return -1; // never } int update(Deque<int[]> d, Map<Integer, Integer> m1, Map<Integer, Integer> m2) { int sz = d.size(); while (sz-- > 0) { int[] info = d.pollFirst(); int x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx); for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny); if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (m1.containsKey(nidx)) continue; if (m2.containsKey(nidx)) return step + 1 + m2.get(nidx); d.addLast(new int[]{nx, ny}); m1.put(nidx, step + 1); } } return -1; }}TypeScript 代码：
let n: numberconst p = new Array<number>(10010).fill(0)const dirs = [[0,1],[0,-1],[1,0],[-1,0]]function shortestBridge(g: number[][]): number { function getIdx(x: number, y: number): number { return x * n + y } function find(x: number): number { if (p[x] != x) p[x] = find(p[x]) return p[x] } function union(x: number, y: number): void { p[find(x)] = p[find(y)] } function update(d: Array<Array<number>>, m1: Map<number, number>, m2: Map<number, number>): number { let sz = d.length while (sz-- > 0) { const info = d.shift() const x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx) for (const di of dirs) { const nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny) if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue if (m1.has(nidx)) continue if (m2.has(nidx)) return step + 1 + m2.get(nidx) d.push([nx, ny]) m1.set(nidx, step + 1) } } return -1 } n = g.length for (let i = 0; i < n * n; i++) p[i] = i for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (g[i][j] == 0) continue for (const di of dirs) { const x = i + di[0], y = j + di[1] if (x < 0 || x >= n || y < 0 || y >= n) continue if (g[x][y] == 0) continue union(getIdx(i, j), getIdx(x, y)) } } } let a = -1, b = -1 const d1 = new Array<number[]>(), d2 = new Array<number[]>() const m1 = new Map<number, number>(), m2 = new Map<number, number>() for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (g[i][j] == 0) continue const idx = getIdx(i, j), root = find(idx) if (a == -1) a = root else if (a != root && b == -1) b = root if (a == root) { d1.push([i, j]) m1.set(idx, 0) } else if (b == root) { d2.push([i, j]) m2.set(idx, 0) } } } while (d1.length != 0 && d2.length != 0) { let t = -1 if (d1.length < d2.length) t = update(d1, m1, m2) else t = update(d2, m2, m1) if (t != -1) return t - 1 } return -1}Python 代码：
import queueclass Solution: def shortestBridge(self, g: List[List[int]]) -> int: def getIdx(x, y): return x * n + y def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(x, y): p[find(x)] = p[find(y)] def update(d, cur, other): sz = d.qsize() while sz != 0: x, y = d.get() idx, step = getIdx(x, y), cur.get(getIdx(x, y)) for di in dirs: nx, ny = x + di[0], y + di[1] nidx = getIdx(nx, ny) if nx < 0 or nx >= n or ny < 0 or ny >= n: continue if nidx in cur: continue if nidx in other: return step + 1 + other.get(nidx) d.put([nx, ny]) cur[nidx] = step + 1 sz -= 1 return -1 n = len(g) p = [i for i in range(n * n + 10)] dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] for i in range(n): for j in range(n): if g[i][j] == 0: continue for di in dirs: x, y = i + di[0], j + di[1] if x < 0 or x >= n or y < 0 or y >= n: continue if g[x][y] == 0: continue union(getIdx(i, j), getIdx(x, y)) a, b = -1, -1 d1, d2 = queue.Queue(), queue.Queue() m1, m2 = {}, {} for i in range(n): for j in range(n): if g[i][j] == 0: continue idx, root = getIdx(i, j), find(getIdx(i, j)) if a == -1: a = root elif a != root and b == -1: b = root if a == root: d1.put([i, j]) m1[idx] = 0 elif b == root: d2.put([i, j]) m2[idx] = 0 while not d1.empty() and not d2.empty(): t = -1 if d1.qsize() < d2.qsize(): t = update(d1, m1, m2) else: t = update(d2, m2, m1) if t != -1: return t - 1 return -1- 工夫复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.934 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布