# C++ solution using DFS and hashing the Island

• ``````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;
}
};
``````

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