###### tags: `Leetcode` `medium` `bfs` `array` `python` `c++`

# 695. Max Area of Island

## [題目連結:] https://leetcode.com/problems/max-area-of-island/description/

## 題目:
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```.


## 解題想法:
* 此題為統計每個島的大小，回傳最大的島嶼面積

* 典型的BFS:
* 額外創建同大小的矩陣visited用以判斷當前位置是否已拜訪過
* 遍歷矩陣(i,j):
* 若gird(i,j)為0:
* visited(i,j)=True
* 若grid(i,j)為1:
* visited(i,j)=True
* 進入bfs計算當前所構成的最大面積
* 更新res
* bfs:
* 使用queue紀錄
* 上下左右四個位置
* 每次判斷鄰居是否出界且尚未拜訪過

## Python:

class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        #創個新matrix紀錄每點是否已經訪問過
        m=len(grid)
        n=len(grid[0])
        visited=[[False for _ in range(n)] for _ in range(m)]
        res=0
        #bfs
        def bfs(i, j):
            curLand=0
            que=[(i,j)]
            dirs=[(1,0), (-1,0), (0,1), (0,-1)]
            while que:
                curX,curY=que.pop(0)
                curLand+=1
                for dirX,dirY in dirs:
                    tmpX=curX+dirX
                    tmpY=curY+dirY
                    #判斷是否出界且尚未拜訪過
                    if 0<=tmpX<m and 0<=tmpY<n and visited[tmpX][tmpY]==False:
                        if grid[tmpX][tmpY]==1: #若grid為1加入que
                            que.append((tmpX,tmpY))
                        visited[tmpX][tmpY]=True #無論1or0皆設為拜訪過ㄌ
            return curLand

        #遍歷矩陣
        for i in range(m):
            for j in range(n):
                if visited[i][j]==False:
                    if grid[i][j]==0:
                        visited[i][j]=True
                    else:
                        visited[i][j]=True
                        #紀錄當前island所構成面積
                        curLand=bfs(i, j)
                        res=max(res, curLand)
        return res

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]]
result=Solution()
ans=result.maxAreaOfIsland(grid)
print(ans)

## C++:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size(), n=grid[0].size(), res=0;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dirs{ {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (visited[i][j]==false){
                    if (grid[i][j]==0)
                        visited[i][j]=true;
                    else{
                        visited[i][j]=true;
                        int curLand=0;
                        queue<pair<int, int>> que;
                        que.push({i, j});
                        while (!que.empty()){
                            auto cur=que.front(); que.pop();
                            curLand+=1;
                            for (auto& dir: dirs){
                                int tmpX=cur.first+dir[0];
                                int tmpY=cur.second+dir[1];
                                if (0>tmpX || tmpX>=m || 0>tmpY || tmpY>=n || visited[tmpX][tmpY]==true) continue;
                                if (grid[tmpX][tmpY]==1)
                                    que.push({tmpX,tmpY});
                                visited[tmpX][tmpY]=true;
                            }
                        }
                        res=max(res, curLand);
                    }
                }
            }
        }
        return res;
    }
};