C++ solution using DFS and hashing the Island


  • 0
    G
    class Solution {
    public:
        
        struct Island{
            vector<pair<int,int> > composeOf;
            
            bool operator==(const Island &other){
         
                if(other.composeOf.size() != composeOf.size()){
                    return false;
                }
                
                int xDiff= other.composeOf[0].first - composeOf[0].first;
                int yDiff = other.composeOf[0].second - composeOf[0].second;
                
                for(int i = 1; i < other.composeOf.size(); ++i){
                    if(other.composeOf[i].first - xDiff != composeOf[i].first ||
                       other.composeOf[i].second - yDiff != composeOf[i].second){
                        return false;
                    }
                }   
                return true;
            }
        };
        
        unordered_map<int,vector<Island*> >islands;
        const vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
       
        void visit(vector<vector<int> > &grid, int i , int j, Island *island){
            island->composeOf.push_back({i,j});
            grid[i][j] = 0;
            
            for(auto &d : dirs){
                int newi = i + d.first;
                int newj = j + d.second;
                
                if(newi >= 0 && newi < grid.size() && newj >=0 && newj < grid[i].size() && grid[newi][newj]){
                    visit(grid,newi,newj,island);
                }
            }
        }
        
        int numDistinctIslands(vector<vector<int>>& grid) {
            int count = 0;
            
            for(int i = 0; i < grid.size(); i++){
                for(int j = 0; j < grid[i].size(); ++j){
                    if(grid[i][j]){
                        Island *island = new Island;
                        visit(grid,i,j,island);
                        int islandSize = island->composeOf.size();
                        bool foundSym = false;
                        
                        for(auto &isl : islands[islandSize]){
                            if(*isl == *island){
                                foundSym = true;
                                break;
                            }
                        }
                        
                        if(!foundSym){
                            count++;
                            islands[islandSize].push_back(island);
                        }
                        else{
                            delete island;
                        }
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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