0695. 岛屿的最大面积

0695. 岛屿的最大面积 #

  • 标签:搜索
  • 难度:中等

题目大意 #

给定一个只包含 01 元素的二维数组,1 代表岛屿,0 代表水。一座岛的面积就是上下左右相邻的 1 所组成的连通块的数目。

要求:计算出最大的岛屿面积。

解题思路 #

使用深度优先搜索方法。遍历二维数组的每一个元素,对于每个值为 1 的元素,记下其面积。然后将该值置为 0(防止二次重复计算),再递归其上下左右四个位置,并将深度优先搜索搜到的值为 1 的元素个数,进行累积统计。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def dfs(self, grid, i, j):
        n = len(grid)
        m = len(grid[0])
        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == 0:
            return 0
        ans = 1
        grid[i][j] = 0
        ans += self.dfs(grid, i + 1, j)
        ans += self.dfs(grid, i, j + 1)
        ans += self.dfs(grid, i - 1, j)
        ans += self.dfs(grid, i, j - 1)
        return ans

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    ans = max(ans, self.dfs(grid, i, j))
        return ans
本站总访问量  次  |  您是本站第  位访问者