Re: [閒聊] 每日leetcode

[involution ( )]

959. Regions Cut By Slashes

第一感就是切成四塊做 union find

可是感覺寫起來挺瑣碎的 覺得medium有這麼搞剛嗎

但想了一下也沒想到比較漂亮的解法

實際寫起來行數很多 不過蠻直觀的 把該合併的合併就ok了


```
struct UnionFind {
    int count;
    vector<int> parent, rank;
    UnionFind(int n) {
        parent = vector<int>(n);
        rank = vector<int>(n);
        iota(parent.begin(), parent.end(), 0);
        count = n;
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return (parent[x] = find(parent[x]));
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y])
            swap(x, y);
        parent[y] = x;
        count -= 1;
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        /*
         *    \ 0 /
         *     \ /
         *    1 X 2
         *     / \
         *    / 3 \
         */

        int n = grid.size();
        auto get = [=](int r, int c) {
            return (r * n + c) * 4;
        };
        int total = n * n * 4;
        UnionFind uf(total);
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int base = get(r, c);
                int up = get(r - 1, c) + 3;
                int left = get(r, c - 1) + 2;
                if (r > 0) uf.merge(base, up);
                if (c > 0) uf.merge(base + 1, left);

                if (grid[r][c] == ' ') {
                    uf.merge(base, base + 1);
                    uf.merge(base, base + 2);
                    uf.merge(base, base + 3);
                } else if (grid[r][c] == '/') {
                    uf.merge(base, base + 1);
                    uf.merge(base + 2, base + 3);
                } else if (grid[r][c] == '\\') {
                    uf.merge(base, base + 2);
                    uf.merge(base + 1, base + 3);
                } else {
                    std::unreachable();
                }
            }
        }
        return uf.count;
    }
};
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723250718.A.B45.html
推 argorok: 大師
推 dont: 大師
推 smart0eddie: 大師