当前位置：首页 > article >正文

695. 岛屿的最大面积

article 2024/9/22 19:07:29

在这里插入图片描述
思路：

只有当前是陆地，才会构成岛屿

当前是陆地，进入回溯

往当前的上、下、左、右位置分别找陆地位置，为陆地

1>标记为2:代表已经遍历过的陆地

2>记录当前方向的陆地总数

以当前陆地组成的岛屿面积=当前陆地面积+向上的陆地面积+向下的陆地面积+向左的陆地面积+向右的陆地面积

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        row= len(grid)
        col=len(grid[0])
        s=[]
        def dfs(i, j, count):
            #找到底
            if not (i >= 0 and i < row) or not (j >= 0 and j < col):
                return count
            if grid[i][j] != 1:
                return count
            grid[i][j] = 2
            down=dfs(i - 1, j, 0)
            up=dfs(i + 1, j, 0)
            left=dfs(i, j - 1, 0)
            right=dfs(i, j + 1, 0)
            return 1+down+up+left+right
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j]==1:
                   res=max(res,dfs(i,j,0))
                    
        return res