brain dead, no hash, straightforward solution


  • 1
    J

    A straightforward solution, note isReflection() and is90()

    class Solution {
        struct point {
            int x, y;
            point(int x_, int y_) :x(x_), y(y_) {;}
            bool operator<(const point& other) const {
                if (other.y == y) {
                    return other.x < x;
                }
                return other.y < y;
            }
    
            bool operator!=(const point& other) const {
                return x != other.x || y != other.y; // or !(*this < other) && !(*this > other)
            }
    
            bool operator==(const point& other) const {
                return !(*this != other);
            }
        };
    
        int n, m;
    
        const vector<int> dx {-1, 0, 1, 0};
        const vector<int> dy {0, 1, 0, -1};
    
        point getNext(int i, int x, int y) {
            return point{x + dx[i], y + dy[i]};
        }
    
        bool inBound(point& p) {
            return p.x >= 0 && p.x < n && p.y >= 0 && p.y <m;
        }
    
        void collector(vector<point>& points, int x, int y, vector<vector<int>>& grid) {
            deque<point> q;
            q.emplace_back(x, y);
            int minx = x, miny = y;
            while(!q.empty()) {
                auto top = q.front();
                q.pop_front();
                points.push_back(top);
                for (int i = 0; i < 4; ++i) {
                    auto next = getNext(i, top.x, top.y);
                    if (inBound(next) && grid[next.x][next.y]) {
                        grid[next.x][next.y] = 0;
                        q.emplace_back(next.x, next.y);
                        minx = min(minx, next.x);
                        miny = min(miny, next.y);
                    }
                }
            }
            for (auto& p: points) {
                p.x -= minx;
                p.y -= miny;
            }
            sort(points.begin(), points.end());
        }
    
        bool isReflection(vector<point>& l, vector<point> r) {
            if (l.size() != r.size()) return false;
            int minx = INT_MAX;
            for (int i = 0; i < r.size(); ++i) {
                r[i].x = -r[i].x;
                minx = min(minx, r[i].x);
            }
    
            for (int i = 0; i < r.size(); ++i) {
                r[i].x -= minx;
            }
    
            sort(r.begin(), r.end());
            return l == r;
        }
    
        // rotate r
        bool is90(vector<point>& l, vector<point>& r) {
            if (l.size() != r.size()) return false;
            int minx = INT_MAX, miny = INT_MAX;
            for (int i = 0; i < r.size(); ++i) {
                int oldx = r[i].x, oldy = r[i].y;
                r[i].x = oldy; r[i].y = -oldx;
                minx = min(minx, r[i].x);
                miny = min(miny, r[i].y);
            }
    
            for (int i = 0; i < r.size(); ++i) {
                r[i].x -= minx; r[i].y -= miny;
            }
    
            sort(r.begin(), r.end());
            return l == r;
        }
    
    public:
        int numDistinctIslands2(vector<vector<int>>& grid) {
            vector<vector<point>> islands;
            unordered_set<int> index;
            n = grid.size();
            if (0 == n) return 0;
            m = grid[0].size();
            for (int x = 0; x < n; ++x) {
                for (int y = 0; y < m; ++y) {
                    if (1 == grid[x][y]) {
                        grid[x][y] = 0;
                        islands.emplace_back();
                        index.insert(islands.size() - 1);
                        collector(islands.back(), x, y, grid);
                    }
                }
            }
            auto cur = index.begin();
            while (cur != index.end()) {
                auto itor = std::next(cur);
                while (itor != index.end()) {
                    bool eq = false;
                    for (auto r : {90, 180, 270, 360}) {
                        if (is90(islands[*cur], islands[*itor]) ||
                            isReflection(islands[*cur], islands[*itor])) {
                            itor = index.erase(itor);
                            eq = true;
                            break;
                        }
                    }
    
                    if (!eq) {
                        itor++;
                    }
                }
                cur++;
            }
            return index.size();
        }
    };
    

    Post here for reference, but a hashed version would be much better in terms of runtime though.


Log in to reply
 

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