題目描述:
給定一個 m x n 的二元矩陣 grid,其中 0 代表海洋、1 代表陸地。你可以沿上下左右移動。求無法走到邊界的陸地格子數(即被海洋完全包圍的陸地)。
解題思路: 邊界 DFS/BFS 消除法:
所有能到達邊界的陸地都是「可逃脫」的,不計入答案。
1 執行 DFS(或 BFS),將它們及其連通的所有 1 標記為已訪問(例如改為 0)。1 的數量,即為被包圍的陸地(飛地)。時間複雜度: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 更簡潔。