<gh_stars>1-10
"""You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally
(horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:
Input: grid = [[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]]

Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1."""


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        self.maps = grid
        self.n = len(grid)
        self.m = len(grid[0])

        for i, j in product(range(self.n), range(self.m)):
            if self.maps[i][j]:
                ans = max(ans, self.trav(i, j))
        return ans

    def trav(self, i, j):
        if i < 0 or j < 0 or i >= self.n or j >= self.m or self.maps[i][j] == 0:
            return 0
        self.maps[i][j] = 0
        return 1 + self.trav(i - 1, j) + self.trav(i + 1, j) + self.trav(i, j - 1) + self.trav(i, j + 1)

# Submission Details:
# >95%/>60%

"""You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally
(horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:
Input: grid = [[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]]

Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1."""


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        self.maps = grid
        self.n = len(grid)
        self.m = len(grid[0])

        for i, j in product(range(self.n), range(self.m)):
            if self.maps[i][j]:
                ans = max(ans, self.trav(i, j))
        return ans

    def trav(self, i, j):
        if i < 0 or j < 0 or i >= self.n or j >= self.m or self.maps[i][j] == 0:
            return 0
        self.maps[i][j] = 0
        return 1 + self.trav(i - 1, j) + self.trav(i + 1, j) + self.trav(i, j - 1) + self.trav(i, j + 1)

# Submission Details:
# >95%/>60%
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid. If there is no island, return 0.  Example 1: Input: grid = [[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]]  Output: 6 Explanation: The answer is not 11, because the island must be connected 4-directionally.  Example 2: Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0  Constraints:  m == grid.length n == grid[i].length 1 <= m, n <= 50 grid[i][j] is either 0 or 1. # Submission Details: # >95%/>60%