岛屿的最大面积

https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1034/

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

image.png

这个是典型的dfs问题，每个节点，碰到不为1的，就去他四个方向（上下左右）看下是否有1的，有的话就继续+1，并且注意把当前遍历过的节点重置为-1，知道遇到所有的节点都没有1。

class Solution(object):
    
    direct = [[0,1],[0,-1],[1,0],[-1,0]]
    step = 0
    
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        max_island = 0
        
        for i in range(0,len(grid)):
            for j in range(0,len(grid[0])):
                if grid[i][j]>0:
                    self.step = 0
                    self.dfs(grid,i,j)
                    max_island = max(self.step,max_island)
        return max_island
    
    
    def dfs(self,grid,i,j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]<1:
            return
        grid[i][j] = -1
        self.step += 1
        for each_dir in self.direct:
            self.dfs(grid,i+each_dir[0],j+each_dir[1])