1020. 飞地的数量

1020. 飞地的数量 #

  • 标签:深度优先搜索、广度优先搜索、并查集、数组、矩阵
  • 难度:中等

题目大意 #

给定一个二维数组 grid,每个单元格为 0(代表海)或 1(代表陆地)。我们可以从一个陆地走到另一个陆地上(朝四个方向之一),然后从边界上的陆地离开网络的边界。

要求:返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

解题思路 #

与四条边界相连的陆地单元是肯定能离开网络边界的。先通过深度优先搜索将与四条边界相关的陆地全部变为海(赋值为 0)。然后统计网格中 1 的数量即为答案。

代码 #

 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
class Solution:
    directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(self, grid, i, j):
        rows = len(grid)
        cols = len(grid[0])
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == 0:
            return
        grid[i][j] = 0

        for direct in self.directs:
            new_i = i + direct[0]
            new_j = j + direct[1]
            self.dfs(grid, new_i, new_j)

    def numEnclaves(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        for i in range(rows):
            if grid[i][0] == 1:
                self.dfs(grid, i, 0)
            if grid[i][cols - 1] == 1:
                self.dfs(grid, i, cols - 1)

        for j in range(cols):
            if grid[0][j] == 1:
                self.dfs(grid, 0, j)
            if grid[rows - 1][j] == 1:
                self.dfs(grid, rows - 1, j)

        ans = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    ans += 1
        return ans
本站总访问量  次  |  您是本站第  位访问者