Leetcode 695 Max Area of Island

题意

给定一个二维矩阵，矩阵中包含0和1，所有相连的1被视为一个岛屿，求这些所有岛屿的最大区域是多少

题目链接

https://leetcode.com/problems/max-area-of-island/description/

题解

遍历二维矩阵，当遇到没有被访问过的1时，开始进行dfs，记此时的1坐标为x,y。 dfs返回从(x,y）出发，能到达的所有岛屿格的数量。

class Solution {
public:
    int m;
    int n;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1 && !vis[i][j]) {
                    res = max(res, dfs(grid, vis, i, j));
                }
            }
        }
        return res;
    }
    
    int dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
        vis[x][y] = true;
        int dk[] = {-1, 0, 1, 0, -1};
        int area = 1;
        for(int i = 0; i < 4; i++) {
            int nx = x + dk[i];
            int ny = y + dk[i+1];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && grid[nx][ny] == 1) {
                area += dfs(grid, vis, nx, ny);
            }
        }
        return area;
    }
};

时间复杂度：$O(mn)$ m，n是二维矩阵的长宽
空间复杂度：$O(mn)$ m，n是二维矩阵的长宽

疑问

为什么area += dfs(grid, vis, nx, ny);， 而不是return 1+dfs(grid, vis, nx, ny)，你需要统计4个方向的答案再返回