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++;
        add(st, pos, m, n);
    }
}

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