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?
- 如果題目改為「找出所有飛地的連通區域數量」而非格子數量,需要如何修改?