# [711. Number of Distinct Islands II] C++, DFS + Set, any comment is welcome.

• Not very fast, but it works.

``````class Solution {
public:
vector<pair<int, int> > dir = {{0,1},{0,-1},{1,0},{-1,0}};
//rotate 90 degree: (i,j)->(j,i)->(j, m - i - 1),
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& check, int i, int j, int m, int n, vector<vector<int>>& pos){
pos.push_back({i,j,n});
check[i][j] = true;
for(auto p : dir){
int ii = i + p.first;
int jj = j + p.second;
if(ii >= 0 && ii < m && jj >= 0 && jj < n && grid[ii][jj] && !check[ii][jj]){
dfs(grid, check, ii, jj, m, n, pos);
}
}
}

void update(unordered_set<string>& st, int& res, vector<vector<int>>& pos, int m, int n){
sort(pos.begin(), pos.end(),[](vector<int> a, vector<int> b){
return  a[0]*a[2] + a[1] < b[0]*b[2] + b[1];
});//need to sort!!!
string s = "";
for(int k = 0; k < pos.size(); ++k){
int i = pos[k][0] - pos[0][0];
int j = pos[k][1] - pos[0][1];
s += to_string(i) + ','+ to_string(j)+';';
}
if(st.find(s) == st.end()){
st.insert(s);
res++;
}
}

void add(unordered_set<string>& st, vector<vector<int>>& pos, int m, int n){
vector<vector<vector<int>>> ind;
ind.resize(7);
for(int k = 0; k < pos.size(); ++k){
int i = pos[k][0];
int j = pos[k][1];
ind[0].push_back({j,m-1-i,m});
ind[1].push_back({m-1-i,n-1-j,n});
ind[2].push_back({n-1-j,i,m});
ind[3].push_back({m-1-i,j,n});
ind[4].push_back({i,n-1-j,n});
ind[5].push_back({j,i,n});
ind[6].push_back({n-1-j,m-1-i,m});
}

for(int k = 0; k < ind.size(); ++k){
string s = "";
sort(ind[k].begin(), ind[k].end(),[](vector<int> a, vector<int> b){
return  a[0]*a[2] + a[1] < b[0]*b[2] + b[1];
});
for(int p = 0; p < ind[k].size(); ++p){
int i = ind[k][p][0] - ind[k][0][0];
int j = ind[k][p][1] - ind[k][0][1];
s += to_string(i) + ','+ to_string(j)+';';
}
st.insert(s);
}
}

int numDistinctIslands2(vector<vector<int>>& grid) {
if(grid.empty()) return 0;

int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> check(m, vector<bool>(n, false));
unordered_set<string> st;
int res = 0;
for(int i = 0; i < grid.size(); ++i){
for(int j = 0; j < grid[0].size(); ++j){
if(!grid[i][j] || check[i][j]) continue;
vector<vector<int>> pos;
dfs(grid, check, i, j, m, n, pos);
update(st, res, pos, m, n);
}
}
return res;
}
};``````

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