c++ dfs solution very easy to understand


  • 0
    Q
    class Solution {
    public:
        int res = 0;
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            if(grid.size() == 0 || grid[0].empty())
                return 0;
            int len1 = grid.size(), len2 = grid[0].size();
            vector<vector<bool>> visited(len1,vector<bool>(len2,false));
            
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    int n = 1;
                    if(visited[i][j] == false && grid[i][j] == 1){
                        dfs(grid,i,j,visited,n);
                    }
                }
            }
            return res;
        }
        
        void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited, int& n){
            res = max(res,n);
            visited[i][j] = true;
            int len1 = grid.size(), len2 = grid[0].size();
            if(check(len1,len2,i+1,j) && grid[i+1][j] == 1 && !visited[i+1][j]){
                n++;
                dfs(grid,i+1,j,visited,n);
            }
            if(check(len1,len2,i,j+1) && grid[i][j+1] == 1 && !visited[i][j+1]){
                n++;
                dfs(grid,i,j+1,visited,n);
            }
            if(check(len1,len2,i-1,j) && grid[i-1][j] == 1 && !visited[i-1][j]){
                n++;
                dfs(grid,i-1,j,visited,n);
            }
            if(check(len1,len2,i,j-1) && grid[i][j-1] == 1 && !visited[i][j-1]){
                n++;
                dfs(grid,i,j-1,visited,n);
            }
            return;
        }
        
        bool check(int i, int j, int m, int n){
            if(m<0 || m >= i || n<0 || n>=j)
                return false;
            else
                return true;
        }
    };
    

Log in to reply
 

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