# Leetcode 695. Max area of islands

## DFS

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.rows = len(grid)
        self.cols = len(grid[0])
        self.directions = [[-1,0],[0,-1],[1,0],[0,1]]
        islands = 0

        def dfs(node: int, island: int):
            x = node // self.cols
            y = node % self.cols

            if grid[x][y] != 1:
                return island

            grid[x][y] = -1
            island += 1

            for _x,_y in self.directions:
                new_x = x + _x
                new_y = y + _y

                if new_x < 0 or new_y < 0 or new_x >= self.rows or new_y >= self.cols:
                    continue
                else:
                    if grid[new_x][new_y] == 1:
                        island = dfs(new_x * self.cols + new_y, island)
            
            return island

        for current in range(self.rows * self.cols):
            x = current // self.cols
            y = current % self.cols
            islands = max(islands,dfs(current,0))
            
        return islands

2023/4/14 AC

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dm = [[-1,0],[0,-1],[0,1],[1,0]]
        output = 0

        def dfs(node: int, c: int):
            x = node // cols
            y = node % cols

            grid[x][y] = 0

            for _x,_y in dm:
                new_x = x + _x
                new_y = y + _y

                if new_x < 0 or new_y < 0 or new_x >= rows or new_y >= cols:
                    continue
                if grid[new_x][new_y] == 1:
                    c = dfs(new_x * cols + new_y, c + 1)
            return c

        for node in range(rows * cols):
            x = node // cols
            y = node % cols
            if grid[x][y] == 1:
                output = max(output, dfs(node, 1))
        
        return output