Leecode #1020. 飞地的数量

给出一个二维数组 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 都在边界上或可以到达边界。

解题思路

题目有点绕，换个思路就是看这个matrix的四周有多少联通的节点，用bfs轻松解题

class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
        rows, cols = len(A), len(A[0])
        drt = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def search(row, col):
            if not A[row][col]:
                return
            A[row][col] = 0
            for col_offset, row_offset in drt:
                _row, _col = row + row_offset, col + col_offset
                if 0 <= _row < rows and 0 <= _col < cols:
                    search(_row, _col)

        for i in range(0, rows):
            search(i, 0)
            search(i, cols - 1)

        for i in range(1, cols-1):
            search(0, i)
            search(rows - 1, i)

        return sum([sum(x) for x in A])