MediumRating 1826

934. Shortest Bridge

arraydepth-first-searchbreadth-first-searchmatrix

在 LeetCode 上作答 ↗

解題說明

Shortest Bridge

題目描述：給定一個 n x n 的二元矩陣 grid，其中恰好有兩個島嶼（由 1 組成的連通區域）。你可以將 0 變為 1，求連接兩個島嶼所需翻轉的最少 0 的數量（即兩島之間的最短距離）。

解題思路： DFS 標記 + BFS 擴展：

DFS 找第一個島：遍歷矩陣找到第一個 1，用 DFS 標記整個島的所有格子（標記為 2），同時將邊界格子加入 BFS 佇列。
BFS 多源擴展：從第一個島的邊界開始，逐層向外擴展（每層距離 +1），直到碰到值為 1 的格子（第二個島），此時的層數即為答案。

C++ 解法

複雜度分析

時間複雜度：O(n^2) — DFS 和 BFS 各自最多遍歷整個矩陣一次。

空間複雜度：O(n^2) — BFS 佇列和 DFS 遞迴棧在最差情況下可能包含 O(n^2) 個元素。

虛擬碼

1. Find any cell with value 1 (part of first island).
2. DFS from that cell:
   a. Mark visited cells as 2.
   b. Add all cells of the first island to BFS queue.
3. BFS level-by-level from the first island:
   a. For each cell in current level, explore 4 neighbors.
   b. If neighbor is 1 (second island), return current step count.
   c. If neighbor is 0, mark as 2, add to queue.
   d. Increment step count after each level.
4. Return step count when second island is reached.

其他解法

雙向 BFS：從兩個島同時開始 BFS 擴展，當兩個搜索前沿相遇時即為答案。可以將搜索空間減半，但實作較複雜。

Union-Find + 排序：將所有水域格子按到兩島的距離排序，逐步合併直到兩島連通。時間 O(n^2 log n)，不如 BFS 直接。

延伸思考

如果矩陣中有超過兩個島，如何找出連接所有島的最小翻轉次數？（提示：最小生成樹）
為什麼用 BFS 而非 DFS 來擴展？DFS 擴展會有什麼問題？
如果允許對角線連接（8 個方向），演算法需要做哪些修改？

Shortest Bridge — CaffeCode