给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
思路：这是一道很显然的深搜题目。通过这道题目对深搜加深的理解，很棒。
~深搜经常用递归来实现
构成递归需具备的条件：
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理
题目要求最大连通块的面积?
遍历每个结点 深搜 更新ans 输出
深搜：定义dfs（x，y）是以(x,y)为起点向外拓展的连通块面积
如果定义(x,y)上下左右结点分别为(x1,y1),(x2,y2),(x3,y3),(x4,y4);
那么dfs（x,y） = dfs(x1,y1)+dfs(x2,y2)+dfs(x3,y3)+dfs(x4,y4)
然后等式右边又可以继续递归下去
递归的基线条件：
????????如果是海洋，返回值一定是0，如果坐标越界，返回值一定是0
如果不越界 且不是海洋，那么初始化sum(返回值：即连通块面积) = 1；
通过上述定义 sum加上四个方向上的增量，然后返回
class Solution {
public:
int dfs(int i,int j,int m,int n,vector<vector<int>>&grid)
{
if (i<0||j<0||i>=m||j>=n) return 0;
if (grid[i][j] ==1 )
{ int sum = 1;
grid[i][j] = 0;
sum+=dfs(i-1,j,m,n,grid);
sum+=dfs(i+1,j,m,n,grid);
sum+=dfs(i,j+1,m,n,grid);
sum+=dfs(i,j-1,m,n,grid);
return sum;
}
return 0;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size(),n = grid[0].size();
for (int i = 0;i<m;i++)
{
for (int j = 0;j<n;j++)
{
ans = max(ans,dfs(i,j,m,n,grid));
}
}
return ans;
}
};奔赴热爱 奔赴山海 坚持算法 数学~
