# Given a non-empty 2D array grid of 0's and 1's, 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.
#
# Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
#
# Example 1:
# [[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]]
# Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
# Example 2:
# [[0,0,0,0,0,0,0,0]]
# Given the above grid, return 0.
# Note: The length of each dimension in the given grid does not exceed 50.


class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        visited = [[False] * len(grid[0]) for _ in xrange(len(grid))]
        m, n = len(grid), len(grid[0])

        ans = 0
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] and not visited[i][j]:
                    ans = max(ans, self.dfs(grid, i, j, visited))

        return ans

    def dfs(self, grid, i, j, visited):
        m, n = len(grid), len(grid[0])
        if i == m or i < 0 or j == n or j < 0 or grid[i][j] == 0 or visited[i][j]:
            return 0

        ans, visited[i][j] = 1, True
        ans += self.dfs(grid, i - 1, j, visited)
        ans += self.dfs(grid, i + 1, j, visited)
        ans += self.dfs(grid, i, j + 1, visited)
        ans += self.dfs(grid, i, j - 1, visited)

        return ans
