695. Max Area of Island

问题：

给定一个由0，1 组成的二维数组，0代表海水，1代表陆地，

求给定数组所形成小岛的最大面积。

Example 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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

　　

解法：DFS

深度优先递归

标记已遍历过为0:  grid[i][j]=0;

向四个方向逐次探索，若不满足条件：超出数组范围or为海水节点0，则直接返回当前面积为0

否则当前面积为1，在以当前节点为轴心，再次向四周探索。每个方向的结果累加，最后返回总面积。

在最外层，顺次遍历整个给定数组，只对 未曾访问过&&陆地节点（grid[i][j]=1）的节点进行上述递归处理。

代码参考：

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int n, int m, int i, int j){
        if(i<0 || i>=n || j<0 || j>=m || grid[i][j] == 0) return 0;
        grid[i][j]=0;
        int area=1;
        area+=dfs(grid, n, m, i-1, j);
        area+=dfs(grid, n, m, i+1, j);
        area+=dfs(grid, n, m, i, j-1);
        area+=dfs(grid, n, m, i, j+1);
        return area;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res=0;
        if(grid.size()==0)return 0;
        int n=grid.size(), m=grid[0].size();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j]==1){
                    res=max(res,dfs(grid, n, m, i, j));
                }
            }
        }
        return res;
    }
};