毎日1題はスラッシュで区域LeetCode 959を区分する

問題を調べ、各セルを4つの小さな三角形と見なし、各小さな三角形をマージします.

//                 ，                          

class UnionFind {
     
public:
    UnionFind(int n): f(n), count(n) {
     
        for (int i = 0; i < n; ++i) {
     
            f[i] = i;
        }
    }

    int findf(int x) {
     
        if (f[x] != x) {
     
            f[x] = findf(f[x]);
        }
        return f[x];
    }

    void unionMerge(int x, int y) {
     
        int fx = findf(x), fy = findf(y);
        if (fx == fy) return;
        f[fy] = fx;
        count--;
    }

    int getCount() {
     
        return count;
    }

private:
    vector<int> f;
    int count;
};

class Solution {
     
public:
    int regionsBySlashes(vector<string>& grid) {
     
        int gridNums = grid.size();
        int traingleSize = 4 * gridNums * gridNums;

        UnionFind uf(traingleSize);
        for (int i = 0; i < gridNums; ++i) {
     
            for (int j = 0; j < gridNums; ++j) {
     
                int index = 4 * (i * gridNums + j);
                char c = grid[i][j];

                //         
                if (c == ' ') {
     
                    //   ，0123    
                    uf.unionMerge(index, index + 1);
                    uf.unionMerge(index, index + 2);
                    uf.unionMerge(index, index + 3);
                }
                else if (c == '/') {
     
                    //   ，  01 23
                    uf.unionMerge(index, index + 1);
                    uf.unionMerge(index + 2, index + 3);
                }
                else if (c == '\\') {
     
                    //    ，  12 03
                    uf.unionMerge(index + 1, index + 2);
                    uf.unionMerge(index, index + 3);
                }

                //          ，                 ，        2       0   ， 3       1     
                if (j < gridNums - 1) {
      //      
                    uf.unionMerge(index + 2, 4 * (i * gridNums + j + 1));
                }
                if (i < gridNums - 1) {
      //      
                    uf.unionMerge(index + 3, 4 * ((i + 1) * gridNums + j) + 1);
                }
            }
        }
        return uf.getCount();
    }
};