给你一个大小为 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; } };
奔赴热爱 奔赴山海 坚持算法 数学~
