DFS:695. Max Area of Island

这道题的意思是，给一个表格，由0或者1填充，求相连的1的最大面积。

这道题我开辟了一个和表格一样大的二维数组，用于记录这个点是否已经计算过了。dfs这个函数返回的是，当前点所在的一片1的面积。

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

讨论区一个java代码：

public int maxAreaOfIsland(int[][] grid) {
        int max_area = 0;
        for(int i = 0; i < grid.length; i++)
            for(int j = 0; j < grid[0].length; j++)
                if(grid[i][j] == 1)max_area = Math.max(max_area, AreaOfIsland(grid, i, j));
        return max_area;
    }
    
    public int AreaOfIsland(int[][] grid, int i, int j){
        if( i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
            grid[i][j] = 0;
            return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
        }
        return 0;
    }