695.-max-area-of-island.md

695. Max Area of Island

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ## 这题没做过很好
        ## 这题不就是染色题，
        ## In the number of island, we count the island, when we meet a "1" in the matrix.
        ## Meanwhile we transform the related land of the island from 1 to 0, to avoid double counting
        
        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_count(i,j,grid))        
        return ans
        
    def dfs_count(self, i, j, grid):
        stack = [(i,j)]
        visited = set()
        ans = 1
        while stack:
            x, y = stack.pop()
            visited.add((x,y))
            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                newx = x + dx
                newy = y + dy
                if 0 <= newx < len(grid) and 0 <=newy<len(grid[0]) and (newx,newy) not in visited and grid[newx][newy] == 1:
                    grid[newx][newy] = 0
                    ans += 1
                    stack.append((newx,newy))
                
                
        return ans
        ## BFS 迭代同理