# 695. Max Area of Island

{% embed url="<https://leetcode.com/problems/max-area-of-island/>" %}

找岛问题都是一个套路...

{% content-ref url="connectivity/200.-number-of-islands" %}
[200.-number-of-islands](https://xuqiangwen1994.gitbook.io/practice/connectivity/200.-number-of-islands)
{% endcontent-ref %}

{% content-ref url="connectivity/130.-surrounded-regions" %}
[130.-surrounded-regions](https://xuqiangwen1994.gitbook.io/practice/connectivity/130.-surrounded-regions)
{% endcontent-ref %}

优先拿`BFS`做，简单点，每次找到新岛就`queue`下去，也可以`DFS`，把`queue`改成`stack`就算一种，或者换成`recursive`写法。

{% tabs %}
{% tab title="BFS" %}

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return res
        
        res = 0
        m, n = len(grid), len(grid[0])
        memo = set()
        
        def validNext(x, y):
            valid = [(i, j )for (i, j) in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] if (i,j) not in memo and 0<= i<m and 0<=j<n]
            return valid
    
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if (x, y) in memo: continue
                if grid[x][y] == 1:
                    area = 0
                    q = collections.deque([(x, y)])
                    while q:
                        x_s, y_s = q.popleft()
                        memo.add((x_s, y_s))
                        area += 1
                        _next = validNext(x_s, y_s)
                        for x_n, y_n in _next:
                            memo.add((x_n, y_n))
                            if grid[x_n][y_n] == 1: q.append((x_n, y_n))
                    res = max(res, area)
        return res
```

{% endtab %}

{% tab title="DFS Recursive" %}

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return res
        
        res = 0
        m, n = len(grid), len(grid[0])
        memo = set()
        
        def valid(x, y):
            if 0<=x<m and 0<=y<n and (x, y) not in memo: return True
        
        def dfs(x, y):
            if not valid(x, y) or grid[x][y] == 0: return 0
            memo.add((x, y))
            count = 1
            for x_n, y_n in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
                count += dfs(x_n, y_n)
            return count
    
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                area = dfs(x, y)
                res = max(res, area)
                
        return res
```

{% endtab %}
{% endtabs %}
