题意理解

地图是一个矩阵，每个格子里面是0或者1。格子的上下左右视为相邻，即连在一起。要求最大的岛屿面积就是求连在一起的1的个数最多是多少。

方法一

深度优先搜索
对于每一个格子，我们有上下左右四个方向，如果相邻的格子是1，那么就可以向这个方向移动，面积加1。 我们使用pass数组记录每个格子是否遍历过，没有遍历过且值为1的格子才可以走上去，否则都不行。注意这里不是在寻找路径，所以在递归后pass不回退，否则会导致面积计算错误。

在主程序中，我们遍历矩阵grid，遇到格子值为1就进行一次dfs，得到一个连在一起的1的个数，更新一次最大值。

演示过程如下，红点表示当前所在位置：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int x[4] = {-1,1,0,0};
    int y[4] = {0,0,-1,1};
    int s = 0;
    vector<vector<bool>> pass;
    
    void dfs(vector<vector<int>>& grid, int i, int j) {
        for (int k=0;k<4;k++)
        {
            //注意边界
            if (i+x[k]>-1 && i+x[k]<grid[0].size() &&
                j+y[k]>-1 && j+y[k]<grid.size() &&
                pass[i+x[k]][j+y[k]]==false &&
                grid[i+x[k]][j+y[k]] == 1)
            {
                pass[i+x[k]][j+y[k]] = true;
                s++;
                dfs(grid, i+x[k], j+y[k]);
            }
        }
        return;
    }
    
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        int ans = 0;
        vector<bool> temp;
        //初始化pass
        for (int i=0;i<grid[0].size();i++)
            temp.push_back(false);
        for (int i=0;i<grid.size();i++)
            pass.push_back(temp);
        //遍历grid
        for (int i=0;i<grid.size();i++)
        {
            for (int j=0;j<grid[0].size();j++)
            {
                if (grid[i][j])
                {
                    //当前位置pass设置为true
                    pass[i][j] = true;
                    s = 1;
                    dfs(grid, i, j);
                    ans = max(ans, s);
                }
            }
        }
        return ans;
    }
};

时间复杂度： $O(NM)O(NM)$。由于pass没有回退，每一块岛屿仅被扫描一遍，所以每一个格子都被扫描过一遍且仅被扫描过一遍。
空间复杂度： $O(NM)O(NM)$。开辟了新的数组pass，大小和grid一致；递归栈的深度也为NM。

方法二

宽度优先搜索
额外使用一个队列实现宽度优先搜索，以起点为中心向四周探查相邻的格子值是否为1。其余的注意点和深度优先搜索一致。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int x[4] = {-1,1,0,0};
    int y[4] = {0,0,-1,1};
    int s = 0;
    queue<pair<int,int>> q;
    vector<vector<bool>> pass;
    
    void bfs(vector<vector<int>>& grid, int i, int j) {
        //坐标(i,j)周围的格子没有扫描过，那么它就要先进入队列
        q.push({i,j});
        while (!q.empty())
        {
            //从队列头部弹出
            auto coordinate = q.front();
            q.pop();
            for (int k=0;k<4;k++)
            {
                int xx = coordinate.first + x[k], yy = coordinate.second +y[k];
                if (xx>-1 && xx<grid.size() && yy>-1 && yy<grid[0].size()
                   && pass[xx][yy]==false && grid[xx][yy])
                {
                    pass[xx][yy] = true;
                    s++;
                    bfs(grid, xx, yy);
                }
            }
        }
        return;
    }
    
    int maxAreaIsland(vector<vector<int> >& grid) {
        // write code here
        int ans = 0;
        vector<bool> temp;
        //初始化pass
        for (int i=0;i<grid[0].size();i++)
            temp.push_back(false);
        for (int i=0;i<grid.size();i++)
            pass.push_back(temp);
        //遍历grid
        for (int i=0;i<grid.size();i++)
        {
            for (int j=0;j<grid[0].size();j++)
            {
                if (grid[i][j])
                {
                    //当前位置pass设置为true
                    pass[i][j] = true;
                    s = 1;
                    bfs(grid, i, j);
                    ans = max(ans, s);
                }
            }
        }
        return ans;
    }
};

时间复杂度： $O(NM)O(NM)$。由于pass没有回退，每一块岛屿仅被扫描一遍，所以每一个格子都被扫描过一遍且仅被扫描过一遍。
空间复杂度： $O(NM)O(NM)$。开辟了新的数组pass，大小和grid一致；队列q的长度也为格子的总数。