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


  • 0

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

Log in to reply
 

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