Accepted DFS C++ Solution


  • 3
    B

    By using the same DFS approach as in "Number of Distinct Island", we can calculate the number of "distinct" islands by hashing. The DFS part is trivial, the real challenge is how to calculate (hash) the "Shape" of an island.

    Here is my AC C++ implementation using primes as parameters when calculating the hash.

    The parameters were carefully chosen as some islands of distinct shapes will collapse into the same hash value If we change some parameter ... :-(

    Point it out if you find it fails on certain test cases.

    Updated
    A better compute_hash function was given below in the same thread.

    class Solution {
    public:
        int numDistinctIslands2(vector<vector<int>>& grid) {
            int m = grid.size();
            if (m == 0) return 0;
            int n = grid[0].size();
            if (n == 0) return 0;
            
            std::unordered_set<int> signatures;
            for (int r = 0; r < m; ++r) {
                for (int c = 0; c < n; ++c) {
                    if (grid[r][c]) {
                        vector<pair<int, int>> pts;
                        visit(grid, m, n, r, c, pts);
                        int hash = compute_hash(pts);
                        signatures.insert(hash);
                    }
                }
            }
            
            return signatures.size();
        }
        
    private:
        int compute_hash(vector<pair<int, int>>& pts) {
            int n = pts.size();
            int hash = 0;
            int xmin = INT_MAX, ymin = INT_MAX, xmax = INT_MIN, ymax = INT_MIN;
            for (int i = 0; i < n; ++i) {
                const auto& pt1 = pts[i];
                xmin = std::min(xmin, pt1.first);
                ymin = std::min(ymin, pt1.second);
                xmax = std::max(xmax, pt1.first);
                ymax = std::max(ymax, pt1.second);
                for (int j = i + 1; j < n; ++j) {
                    const auto& pt2 = pts[j];
                    int delta_x = pt1.first - pt2.first;
                    int delta_y = pt1.second - pt2.second;
                    if (delta_x == 0 || delta_y == 0) {
                        hash += 19 * (delta_x * delta_x + delta_y * delta_y);
                    } else {
                        hash += 31 * (delta_x * delta_x + delta_y * delta_y);
                    }
                    
                }
            }
    
            
            int delta_x = xmax - xmin, delta_y = ymax - ymin;
            hash += 193 * (delta_x * delta_x + delta_y * delta_y) + 97 * delta_x * delta_y;
            return hash;
        }
        
        int compute_hash_improved(vector<pair<int, int>>& pts) {
            int n = pts.size();
            int hash = 0;
            std::unordered_map<int, int> stats1, stats2;
            
            for (int i = 0; i < n; ++i) {
                const auto& pt1 = pts[i];
                stats1[pt1.first]++;
                stats2[pt1.second]++;
                for (int j = i + 1; j < n; ++j) {
                    const auto& pt2 = pts[j];
                    int delta_x = pt1.first - pt2.first;
                    int delta_y = pt1.second - pt2.second;
                    if (delta_x == 0 || delta_y == 0) {
                        hash += 19 * (delta_x * delta_x + delta_y * delta_y);
                    } else {
                        hash += 31 * (delta_x * delta_x + delta_y * delta_y);
                    } 
                }
            }
            
            for (auto& kv : stats1) {
                hash += 73 * kv.second * kv.second;
            }
            for (auto& kv : stats2) {
                hash += 73 * kv.second * kv.second;
            }
            
            int delta_x = stats1.size(), delta_y = stats2.size();
            hash += 193 * (delta_x * delta_x + delta_y * delta_y) + 97 * delta_x * delta_y;
            return hash;
        }
    
        void visit(vector<vector<int>>& grid, int m, int n, int r, int c,
                   vector<pair<int, int>>& pts) {
            bool outOfBound = (r < 0 || r >= m || c < 0 || c >= n);
            if (outOfBound || grid[r][c] == 0) return;
            
            grid[r][c] = 0;
            pts.emplace_back(r, c);
            visit(grid, m, n, r - 1, c, pts);
            visit(grid, m, n, r + 1, c, pts);
            visit(grid, m, n, r, c - 1, pts);
            visit(grid, m, n, r, c + 1, pts);
        }    
    };
    

  • 1
    J

    Could you please give some explanation on your hashing function? It's kind of abstract. Thank you!


  • 0
    B

    @JadenPan As to the hash function,

    1. First, we take into consideration the "width" (which is abs(xmax - xmin) ), and "height" ( abs(ymax - ymin) ) of the island.

    2. Meanwhile, the Euclidean distance of every two "points" of the island was calculated into the final hash value, and this is why the loop for j.

    for (int j = i + 1; j < n; ++j) {
    ...
    }
    
    1. When calculating the euclidean distance, points on the same row/column were differentiated from those not on the same row/column.

    2. If we want to further depict the "shape" of an island, we can take into consideration the population of points along the horizontal/vertical line.

    The following is another compute_hash function got accepted.

        int compute_hash(vector<pair<int, int>>& pts) {
            int n = pts.size();
            int hash = 0;
            std::unordered_map<int, int> stats1, stats2;
            
            for (int i = 0; i < n; ++i) {
                const auto& pt1 = pts[i];
                stats1[pt1.first]++;
                stats2[pt1.second]++;
                for (int j = i + 1; j < n; ++j) {
                    const auto& pt2 = pts[j];
                    int delta_x = pt1.first - pt2.first;
                    int delta_y = pt1.second - pt2.second;
                    if (delta_x == 0 || delta_y == 0) {
                        hash += 19 * (delta_x * delta_x + delta_y * delta_y);
                    } else {
                        hash += 31 * (delta_x * delta_x + delta_y * delta_y);
                    } 
                }
            }
            
            for (auto& kv : stats1) {
                hash += 73 * kv.second * kv.second;
            }
            for (auto& kv : stats2) {
                hash += 73 * kv.second * kv.second;
            }
            
            int delta_x = stats1.size(), delta_y = stats2.size();
            hash += 193 * (delta_x * delta_x + delta_y * delta_y) + 97 * delta_x * delta_y;
            return hash;
        }
    

  • 0
    J

    @bigoffer4all I got a rough idea, but how dose the prime numbers like 19,31,73 come out? Any strategies on choosing these numbers?


  • 0
    B

    @JadenPan I "stolen" those primes from some of the fastest solutions of "Number of Distinct Islands" which can be seen when you got your solution accepted.

    However, they needn't to be primes, but we have to differentiate different aspects of the "Shape" of an island. A better choice may be by observing the row-by-row(column-by-column) fluctuates of heights(width) and finding out the characteristics.

    FYI.


Log in to reply
 

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