Area massima dell'isola

def max_area_of_island_opt(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r == rows or c < 0 or c == cols or grid[r][c] == 0:
            return 0
        grid[r][c] = 0
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
    area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                area = max(area, dfs(r, c))
    return area

def max_area_of_island_brute(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
    def bfs(r, c):
        q = [(r, c)]
        visited.add((r, c))
        area = 0
        while q:
            row, col = q.pop(0)
            area += 1
            for dr, dc in [[1,0],[-1,0],[0,1],[0,-1]]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    q.append((nr, nc))
        return area
    max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                max_area = max(max_area, bfs(r, c))
    return max_area