1020. 飛地的數量 · ttttt

# 1020. 飛地的數量 ## 題目地址(1020. 飛地的數量) <https://leetcode-cn.com/problems/number-of-enclaves/> ## 題目描述 ``` <pre class="calibre18">``` 給出一個二維數組 A，每個單元格為 0（代表海）或 1（代表陸地）。移動是指在陸地上從一個地方走到另一個地方（朝四個方向之一）或離開網格的邊界。返回網格中無法在任意次數的移動中離開網格邊界的陸地單元格的數量。示例 1：輸入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 輸出：3 解釋：有三個 1 被 0 包圍。一個 1 沒有被包圍，因為它在邊界上。示例 2：輸入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] 輸出：0 解釋：所有 1 都在邊界上或可以到達邊界。提示： 1 <= A.length <= 500 1 <= A[i].length <= 500 0 <= A[i][j] <= 1 所有行的大小都相同 ``` ``` ## 前置知識 - DFS - hashset ## 解法一 (暴力法) ### 思路這是一個典型的可以使用 DFS 進行解決的一類題目， LeetCode 相關的題目有很多。對于這種題目不管是思路還是代碼都有很大的相似性，我們來看下。暴力法的思路很簡單，我們遍歷整個矩陣： - 如果遍歷到 0，我們不予理會 - 如果遍歷到 1. 我們將其加到 temp - 不斷拓展邊界（上下左右） - 如果 dfs 過程中碰到了邊界，說明可以逃脫，我們將累加的 temp 清空 - 如果 dfs 過程之后沒有碰到邊界，說明無法逃脫。我們將 temp 加到 cnt - 最終返回 cnt 即可 ### 關鍵點解析 - visited 記錄訪問過的節點，防止無限循環。 ### 代碼 Python Code: ``` <pre class="calibre18">``` class Solution: temp = 0 meetEdge = False def numEnclaves(self, A: List[List[int]]) -> int: cnt = 0 m = len(A) n = len(A[0]) visited = set() def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or (i, j) in visited: return visited.add((i, j)) if A[i][j] == 1: self.temp += 1 else: return if i == 0 or i == m - 1 or j == 0 or j == n - 1: self.meetEdge = True dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) for i in range(m): for j in range(n): dfs(i, j) if not self.meetEdge: cnt += self.temp self.meetEdge = False self.temp = 0 return cnt ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(M?N)O(M \* N)O(M?N) ## 解法二 (消除法) ## 公司 - 暫無 ### 思路上面的解法空間復雜度很差，我們考慮進行優化，這里我們使用消除法。即使用題目范圍外的數據原地標記是否訪問，這樣時間復雜度可以優化到 O(1)O(1)O(1)，這是一種非常常見的優化技巧，請務必掌握，另外文章末尾的題目也是類似的技巧，大家可以結合起來練習。 - 從矩陣邊界開始 dfs - 如果碰到 1 就將其變成 0 - 如果碰到 0 則什么都不做 - 最后我們遍歷整個矩陣，數一下 1 的個數即可。 ### 關鍵點解析 - dfs 消除法 ### 代碼 Python Code: ``` <pre class="calibre18">``` # # @lc app=leetcode.cn id=1020 lang=python3 # # [1020] 飛地的數量 # # @lc code=start class Solution: def numEnclaves(self, A: List[List[int]]) -> int: cnt = 0 m = len(A) n = len(A[0]) def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or A[i][j] == 0: return A[i][j] = 0 dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) for i in range(m): dfs(i, 0) dfs(i, n - 1) for j in range(1, n - 1): dfs(0, j) dfs(m - 1, j) for i in range(m): for j in range(n): if A[i][j] == 1: cnt += 1 return cnt # @lc code=end ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(1)O(1)O(1) ## 參考 - [200.number-of-islands](https://github.com/azl397985856/leetcode/blob/master/problems/200.number-of-islands.md)