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