leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0959.cpp (2001B)

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