c++ solution easy to understand


  • 0
    Q
    class Solution {
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            if(grid.size() == 0 || grid[0].empty())
                return 0;
            int len1 = grid.size(), len2 = grid[0].size();
            vector<vector<bool>> visited(len1,vector<bool>(len2,false));
            int res = 0;
            set<vector<vector<int>>> s;
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    if(visited[i][j] == false && grid[i][j] == 1){
                        //cout<<"line 12 "<<i<<" "<<j<<endl;
                        vector<pair<int,int>> r;
                        dfs(grid,i,j,visited,r);
                        //cout<<"line 15 "<<r.size()<<endl;
                        vector<vector<int>> t = deal(r);
                        s.insert(t);
                        
                    }
                }
            }
            
            return s.size();
        }
        vector<vector<int>> deal(vector<pair<int,int>> r){
            if(r.size() == 0)
                return vector<vector<int>> {{}};
            int row = r[0].first, col = r[0].second;
            int row_m = row;
            for(auto it:r){
                row = min(row,it.first);
                col = min(col,it.second);
                row_m = max(row_m,it.first);
            }
            vector<vector<int>> res(row_m-row+1,vector<int>{});
            
            for(auto it:r)
                res[it.first - row].push_back(it.second-col);
            return res;
        }
        
        void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited,vector<pair<int,int>> &r){
            if(visited[i][j] == true){
                return;
            }
            
            visited[i][j] = true;
            r.push_back(make_pair(i,j));
            int len1 = grid.size(), len2 = grid[0].size();
            if(check(len1,len2,i+1,j) && grid[i+1][j] == 1)
                dfs(grid,i+1,j,visited,r);
            if(check(len1,len2,i,j+1) && grid[i][j+1] == 1)
                dfs(grid,i,j+1,visited,r);
            if(check(len1,len2,i-1,j) && grid[i-1][j] == 1)
                dfs(grid,i-1,j,visited,r);
            if(check(len1,len2,i,j-1) && grid[i][j-1] == 1)
                dfs(grid,i,j-1,visited,r);
            
            return;
        }
        
        bool check(int i, int j, int m, int n){
            if(m<0 || m >= i || n<0 || n>=j)
                return false;
            else
                return true;
        }
    };
    

Log in to reply
 

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