1020.number-of-enclaves.md

题目地址

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 进行解决的一类题目， 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

解法二 (消除法)

思路

上面的解法时间复杂度和空间复杂度都很差，我们考虑进行优化， 这里我们使用消除法。

• 从矩阵边界开始 dfs
• 如果碰到 1 就将其变成 0
• 如果碰到 0 则什么都不做
• 最后我们遍历整个矩阵，数一下 1 的个数即可。

关键点解析

• dfs 消除法

代码

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

参考

• 200.number-of-islands