leetcode

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 };