'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # T: O(R*C), R/C as the number of rows/cols
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        seen = set()
        
        def area(r, c):
            if not (0 <= r < len(grid) and 0 <= c <len(grid[0]) and (r, c) not in seen and grid[r][c]):
                return 0
            seen.add((r, c))
            return (1 + area(r+1, c) + area(r, c+1) \
                    + area(r-1, c) + area(r, c-1))
        
        return max(area(r, c) for r in range(len(grid)) \
                   for c in range(len(grid[0])))
            
    # iterative dfs
    def maxAreaOfIsland1(self, grid: List[List[int]]) -> int:
        seen = set()
        ans = 0
        for r0, row in enumerate(grid):
            for c0, val in enumerate(row):
                if val and (r0, c0) not in seen:
                    shape = 0
                    stack = [(r0, c0)]
                    seen.add((r0, c0))
                    while stack:
                        r, c = stack.pop()
                        shape += 1
                        for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                                    and grid[nr][nc] and (nr, nc) not in seen):
                                stack.append((nr, nc))
                                seen.add((nr, nc))
                    ans = max(ans, shape)
        return ans


    # self-made, 
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        
        def helper(i, j):
            if not (0 <= i < len(grid) and 0 <= j < len(grid[0]) and (i, j) \
                    not in seen and grid[i][j] == 1):
                return 0
            seen.add((i, j))
            return 1 + helper(i+1, j) + helper(i, j+1)\
             + helper(i-1, j) + helper(i, j-1)
        
        res = 0
        seen = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # if grid[i][j] == 1: 
                tmp = helper(i, j)
                res = max(res, tmp)
        return res