1254. 统计封闭岛屿的数目

发表于 更新于 分类于
1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

问题描述

有一个二维矩阵 grid，每个位置要么是陆地（记号为0 ）要么是水域（记号为1 ）。

我们从一块陆地出发，每次可以往上下左右4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

Example 1

1
2
3
4
输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

Example 2

1
2
输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

Example 3

1
2
3
4
5
6
7
8
输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

题解

全题目最重要的一点就是，如果0岛屿能碰到边界，就不算封闭岛屿。
所以只需要扩散搜索所有的0岛屿，碰到边界就不算就可以了。
注意不要return里面写一串and，短路求值可能导致后面的扩散操作不被执行。

搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from typing import List, Set, Tuple


class Solution:

    def visit(self, grid: List[List[int]], x: int, y: int,
              visited: Set[Tuple[int, int]]) -> bool:

        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            # 走到边界了，表示不是closedIsland
            return False

        if grid[x][y] != 0:
            # 只有0才会触发继续扩散
            return True

        if (x, y) in visited:
            # 走过了就不要再走了
            return True

        visited.add((x, y))
        # 一定要一步一步走，不要一次过and，短路求值会把后面的操作省略
        result = self.visit(grid, x-1, y,  visited)
        result2 = self.visit(grid, x, y-1,  visited)
        result3 = self.visit(grid, x+1, y,  visited)
        result4 = self.visit(grid, x, y+1,  visited)
        return result and result2 and result3 and result4

    def closedIsland(self, grid: List[List[int]]) -> int:
        totalClosedIslandCount = 0
        visited = set()
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if (x, y) not in visited and grid[x][y] == 0 and self.visit(grid, x, y, visited):
                    totalClosedIslandCount += 1

        return totalClosedIslandCount

测试代码

1
2
3
4
5
grid = [[0, 0, 1, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 1, 1, 0]]
solution = Solution()
print(solution.closedIsland(grid))

1

1
2
3
4
5
6
7
8
9
grid = [[1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1],           
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1]]
solution = Solution()
print(solution.closedIsland(grid))

2

1
2
3
4
5
6
7
8
9
10
11
12
grid = [[0, 0, 1, 1, 0, 1, 0, 0, 1, 0],
        [1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 1, 0, 0, 1, 1, 0],
        [0, 1, 1, 0, 0, 0, 0, 1, 0, 1],
        [0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
        [0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
        [1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        [1, 1, 1, 0, 0, 1, 0, 1, 0, 1],
        [1, 1, 1, 0, 1, 1, 0, 1, 1, 0]]
solution = Solution()
print(solution.closedIsland(grid))

5