Self Explanatory C++ Simple Code


  • 1
    B
    class Solution {
    public:
    bool isvalid(int row,int col,int x,int y)
    {
        if(x<row && x>=0 && y<col && y>=0)
        return true;
        return false;
    }
    void DFS(vector <vector <bool> > &visit,int x,int y ,int row,int col , vector<vector<char>>& grid)
    {
        
        visit[x][y]=true;
        // Again call DFS is x,y are valid  , not visited and grid element corresponding to them is '1'
        if(isvalid(row,col,x-1,y) && grid[x-1][y]=='1' && visit[x-1][y]==false)
        DFS(visit,x-1,y,row,col,grid);
        
        if(isvalid(row,col,x,y-1) && grid[x][y-1]=='1' && visit[x][y-1]==false)
        DFS(visit,x,y-1,row,col,grid);
        
        if(isvalid(row,col,x+1,y) && grid[x+1][y]=='1' && visit[x+1][y]==false)
        DFS(visit,x+1,y,row,col,grid);
        
        if(isvalid(row,col,x,y+1) && grid[x][y+1] =='1' && visit[x][y+1]==false)
        DFS(visit, x,y+1,row,col,grid);
        
        
    }
        int numIslands(vector<vector<char>>& grid) {
            if(grid.empty())
                return 0;
            int row=grid.size();
            int col=grid[0].size();
    
            vector <vector <bool> >visit(row, vector <bool >(col));
            int i=0,j=0;
            int c=0;
           for(int i=0;i<row;i++)
           {
               for(int j=0;j<col;j++)
               {
                   if(grid[i][j]=='1' && visit[i][j]==false)
                   {
                       DFS(visit,i,j,row,col,grid);
                       c++;
                       
                   }
               }
           }
            
            return c;
            
        }
    };
    

Log in to reply
 

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