Graph DFS Solution in C++

max_area_islands_graph.cpp

class Solution {
    // denotes the 8 neighbors of a grid cell
    int row_dirs[8] = {0, 0, -1, 1, -1, -1, 1, 1};
    int col_dirs[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
    int rows, cols;
public:
    void dfs_helper(int r, int c, vector<vector<int>> &grid, int &cur_area) {
        // base case: corner cases of the matrix
        // when you encounter 0: there won't be adjacent neighbor calls
        if(r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == 0)
            return;
        
        // mark the current block of 1 as visited
        grid[r][c] = 0;
        cur_area++;
        // recursive dfs calls in 8 directions
        for(int itr = 0; itr < 8; itr++)
            dfs_helper(r + row_dirs[itr], c + col_dirs[itr], grid, cur_area);
    }

    //Function to find unit area of the largest region of 1s.
    int findMaxArea(vector<vector<int>>& grid) {
        // Code here
        int max_area = 0, cur_area;
        this->rows = grid.size();
        this->cols = grid[0].size();
        
        // initiate dfs call for every component
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(grid[i][j] == 1) {
                    cur_area = 0;
                    dfs_helper(i, j, grid, cur_area);
                    if(cur_area > max_area)
                        max_area = cur_area;
                }
            }
        }
        return max_area;
    }
};