Easy to understand C++ recursive DFS


  • 0

    Summary: Use DFS to find contiguous chunks of 1s, increment area count by 1 for each neighbor cell which is also part of the island ( i.e. neighbor cell has value of 1 ), and "sink" each island cell included in the ongoing count ( i.e. set the cell value to 0 ).

    class Solution {
    public:
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            int m=0;
            for (int r=0; r<grid.size(); ++r){
                for (int c=0; c<grid[0].size(); ++c){
                    if (grid[r][c]){
                        int curr=dfs(grid,r,c);
                        m=max(m,curr);
                    }
                }
            }
            return m;
        }
        
    private:
        int dfs(vector<vector<int>>& grid, int r, int c){
            if (!(0<=r&&r<grid.size() && 0<=c&&c<grid[0].size())) return 0;
            if (!grid[r][c]) return 0;
            grid[r][c]=0;
            return 1
                +dfs(grid,r-1,c)  // top
                +dfs(grid,r,c+1)  // right
                +dfs(grid,r+1,c)  // bottom
                +dfs(grid,r,c-1); // left
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.