0959.cpp (2001B)
1 class UnionFind { 2 vector<int> root, rank; 3 int n; 4 5 public: 6 UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); } 7 8 int find(int x) { 9 while (x != root[x]) 10 x = root[x] = root[root[x]]; 11 return x; 12 } 13 14 void join(int x, int y) { 15 x = find(x), y = find(y); 16 17 if (x != y) { 18 if (rank[x] > rank[y]) swap(x, y); 19 20 root[x] = y; 21 rank[y] += rank[x]; 22 } 23 } 24 25 int count() { 26 int cnt = 0; 27 for (int i = 0; i < n; i++) 28 cnt += root[i] == i; 29 return cnt; 30 } 31 32 void set_invalid(int x) { root[x] = -1; } 33 }; 34 35 class Solution { 36 int n; 37 38 int get_base_index(int x, int y) { return (n * x + y) * 2; } 39 40 bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; } 41 42 int get_start_offset(char c, int k) { 43 if (c == '/') 44 return (k % 2 == 0) ? 1 : 0; 45 else 46 return (k == 0 || k == 3) ? 1 : 0; 47 } 48 49 int get_index(char c, int k, int x, int y, bool dest) { 50 int offset = get_start_offset(c, k); 51 if (dest) offset = !offset; 52 return get_base_index(x, y) + (c != ' ') * offset; 53 } 54 55 public: 56 int regionsBySlashes(vector<string> &grid) { 57 n = grid.size(); 58 UnionFind uf(2 * n * n); 59 60 vector<pair<int, int>> offset = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 61 for (int x = 0; x < n; x++) { 62 for (int y = 0; y < n; y++) { 63 for (int k = 0; k < 4; k++) { 64 int nx = x + offset[k].first, ny = y + offset[k].second; 65 if (!valid(nx, ny)) continue; 66 int index = get_index(grid[x][y], k, x, y, 0); 67 int nindex = get_index(grid[nx][ny], k, nx, ny, 1); 68 uf.join(index, nindex); 69 } 70 if (grid[x][y] == ' ') uf.set(get_base_index(x, y) + 1); 71 } 72 } 73 74 return uf.count(); 75 } 76 };