1020. 飞地的数量

题目地址(1020. 飞地的数量)

https://leetcode-cn.com/problems/number-of-enclaves/

题目描述

给出一个二维数组 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:

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(1)$，这是一种非常常见的优化技巧，请务必掌握，另外文章末尾的题目也是类似的技巧，大家可以结合起来练习。

• 从矩阵边界开始 dfs

• 如果碰到 1 就将其变成 0

• 如果碰到 0 则什么都不做

• 最后我们遍历整个矩阵，数一下 1 的个数即可。

关键点解析

• 原地标记

代码

Python Code:

#
# @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(1)$

参考

• 200.number-of-islands