695岛屿最大面积leetcode -深度优先搜索

题目描述

题解1-深度优先搜索

遍历每个点，在每个点就是使用深度优先搜索，将自身变为0同时计算周围四个点，方法做完后发现与题解1相同复杂度为

class Solution:
    def dfs_single(self,grid,cur_x,cur_y):
        if cur_x<0 or cur_y<0 or cur_x>len(grid)-1 or cur_y>len(grid[0])-1 or grid[cur_x][cur_y]==0 :
            return 0
        ans=1
        grid[cur_x][cur_y]=0
        directon=[(1,0),(-1,0),(0,1),(0,-1)]
        for dx,dy  in directon:
            next_x,next_y=cur_x+dx,cur_y+dy
            ans+=self.dfs_single(grid,next_x,next_y)
        return ans

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_island=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                max_island=max(self.dfs_single(grid,i,j),max_island)
        return max_island