"""
Problem: 695. Max Area of Island
Url: https://leetcode.com/problems/max-area-of-island/
Author: David Wang
Date: 02/17/2021
"""


from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0

        for i, row in enumerate(grid):
            for j, val in enumerate(row):
                if val == 1:
                    size = self.get_island_size(grid, i, j)

                    if size > max_area:
                        max_area = size

        return max_area



    def get_island_size(self, grid, i, j):
        size = 0
        grid[i][j] = 0
        queue = [(i, j)]

        while queue:
            cur = queue.pop()
            size += 1

            edges = [(-1, 0), (0, 1), (1, 0), (0, -1)]

            for edge in edges:
                r, c = edge
                row =  cur[0] + r
                col = cur[1] + c

                if (row < 0 or
                    row > len(grid) - 1 or
                    col < 0 or
                    col > len(grid[0]) - 1):
                    continue

                val = grid[row][col]

                if val == 0:
                    continue

                grid[row][col] = 0

                queue.append((row, col))

        return size

if __name__ == '__main__':
    input = [
        [0,0,1,0,0,0,0,1,0,0,0,0,0],
        [0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,1,0,1,0,0,0,0,0,0,0,0],
        [0,1,0,0,1,1,0,0,1,0,1,0,0],
        [0,1,0,0,1,1,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,0,0],
        [0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,0,0,0,0,0,0,1,1,0,0,0,0],
    ]
    expected = 6
    output = Solution().maxAreaOfIsland(input)
    print(expected, output)
    assert expected == output

    input = [[0, 0, 0, 0, 0, 0, 0, 0]]
    expected = 0
    output = Solution().maxAreaOfIsland(input)
    print(expected, output)
    assert expected == output

    input = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
    expected = 4
    output = Solution().maxAreaOfIsland(input)
    print(expected, output)
    assert expected == output
