MediumRating 1615
1020. Number of Enclaves
arraydepth-first-searchbreadth-first-searchunion-findmatrix
解題說明
Number of Enclaves
題目描述：
給定一個 m x n 的二元矩陣 grid，其中 0 代表海洋、1 代表陸地。你可以沿上下左右移動。求無法走到邊界的陸地格子數（即被海洋完全包圍的陸地）。
解題思路： 邊界 DFS/BFS 消除法：
所有能到達邊界的陸地都是「可逃脫」的，不計入答案。
- 從矩陣的四條邊界出發，對所有邊界上的
1執行 DFS（或 BFS），將它們及其連通的所有1標記為已訪問（例如改為0）。 - 遍歷整個矩陣，計算剩餘的
1的數量，即為被包圍的陸地（飛地）。
C++ 解法
複雜度分析
時間複雜度：O(m * n) — 每個格子最多被訪問一次（DFS 標記 + 最終計數）。
空間複雜度：O(m * n) — DFS 遞迴棧在最差情況下的深度。使用 BFS 可改為 O(min(m, n))。
虛擬碼
1. For each border cell (i, j): If grid[i][j] == 1: DFS/BFS to mark all connected land as visited (set to 0). 2. Count remaining cells with value 1. 3. Return the count.
其他解法
BFS：O(m * n) 時間、O(m * n) 空間。用佇列替代遞迴，避免棧溢出風險。適用於矩陣很大的情況。
Union-Find：O(m * n * alpha(m * n)) 時間。將所有陸地合併，邊界陸地統一連接到一個虛擬節點。最後計算不與虛擬節點連通的陸地數量。適用於動態連通性問題，但本題中 DFS/BFS 更簡潔。
延伸思考
- 本題與 LeetCode 130（Surrounded Regions）有何異同？解法是否可以復用？
- 如果矩陣非常大（10000 x 10000），DFS 可能棧溢出。如何改為迭代式 DFS 或 BFS？
- 如果題目改為「找出所有飛地的連通區域數量」而非格子數量，需要如何修改？