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)