3/15题解

1.给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 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]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
方法一：深度优先搜索

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
         int res=0;
         for(int i=0;i<grid.size();i++)
         {
             for(int j=0;j<grid[0].size();j++)
             {
                 res=max(res,dfs(grid,i,j));
             }
         }
         return res;
    }
    int dfs(vector<vector<int>>& grid,int i,int j)
    {
        int ans=0;
        if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||grid[i][j]!=1)
          return 0;//不符合条件直接返回0
        ans=1;
        grid[i][j]=0;//走过的点都置零不再计算
        int a[4]={0,0,-1,1};
        int b[4]={1,-1,0,0};//上下左右四点
        for(int index=0;index<4;index++)
        {
            int next_i=i+a[index];
            int next_j=j+b[index];
            ans+=dfs(grid,next_i,next_j);//递归，深度搜索上下左右四点，加起来
        }
        return ans;
    }
};

方法二：堆栈实现深度优先搜索

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                int cur=0;
                stack<int> s1,s2;//在循环最内部声明，每次都重置一下
                s1.push(i);
                s2.push(j);
                while(!s1.empty())
                {
                    int cur_i=s1.top();
                    int cur_j=s2.top();
                    s1.pop();
                    s2.pop();
                    if(cur_i<0||cur_j<0||cur_i>=grid.size()||cur_j>=grid[0].size()||grid[cur_i][cur_j]!=1)
                    continue;//不符合条件就continue
                    cur++;
                    grid[cur_i][cur_j]=0;
                    int a[4]={0,0,1,-1};
                    int b[4]={1,-1,0,0};
                    for(int index=0;index<4;index++)
                    {
                        s1.push(cur_i+a[index]);
                        s2.push(cur_j+b[index]);//符合条件就把上下左右都push进去
                    }
                }
                res=max(res,cur);
            }          
        }
        return res;
    }
};

方法三：若把方法二中的堆栈改为队列，就变成了广度优先搜索。