# LeetCode 695Max Area of Island

## LeetCode 695 Max Area of Island Problem

``````class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# because
ans = 0
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
grid[i][j] = 0
ans = max(self.dfs(grid, i, j), ans)
# ans = max(self.bfs(grid, i, j), ans)
return ans

def dfs(self, grid, i, j):
# DFS based on stack
stack = [(i, j)]
area = 0
# Stack for DFS
while stack:
r, c = stack.pop(-1)
area += 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) and grid[nr][nc]):
stack.append((nr, nc))
grid[nr][nc] = 0
return area

# def bfs(self, grid, x, y):
#     # BFS based on queue
#     queue = [(x, y)]
#     area = 0
#     # Stack for DFS
#     while queue:
#         i, j = queue.pop(0)
#         area += 1
#         if i - 1 >= 0 and grid[i - 1][j] == 1:
#             grid[i - 1][j] = 0
#             queue.append((i - 1, j))
#         if i + 1 < len(grid) and grid[i + 1][j] == 1:
#             grid[i + 1][j] = 0
#             queue.append((i + 1, j))
#         if j - 1 >= 0 and grid[i][j - 1] == 1:
#             grid[i][j - 1] = 0
#             queue.append((i, j - 1))
#         if j + 1 < len(grid) and grid[i][j + 1] == 1:
#             grid[i][j + 1] = 0
#             queue.append((i, j + 1))
#     return area

# def maxAreaOfIsland(self, grid):
#     # Recursive DFS
#     seen = set()
#     def area(r, c):
#         if not (0 <= r < len(grid) and 0 <= c < len(grid)
#                 and (r, c) not in seen and grid[r][c]):
#             return 0
#         return (1 + area(r+1, c) + area(r-1, c) +
#                 area(r, c-1) + area(r, c+1))

#     return max(area(r, c)
#                for r in range(len(grid))
#                for c in range(len(grid)))
``````