1
class Solution {
2
  int[] parent;
3
  int[] rank;
4

5
  public int regionsBySlashes(String[] grid) {
6
    parent = new int[4 * grid.length * grid.length];
7
    rank = new int[4 * grid.length * grid.length];
8

9
    for (int i = 0; i < parent.length; i++) {
10
      parent[i] = i;
11
      rank[i] = 0;
12
    }
13

14
    for (int i = 0; i < grid.length; i++) {
15
      for (int j = 0; j < grid[i].length(); j++) {
16
        char ch = grid[i].charAt(j);
17

18
        int bno = i * grid.length + j;
19

20
        if (ch != '/') {
21
          unionHelper(4 * bno + 0, 4 * bno + 1);
22
          unionHelper(4 * bno + 2, 4 * bno + 3);
23
        }
24

25
        if (ch != '\\') {
26
          unionHelper(4 * bno + 0, 4 * bno + 3);
27
          unionHelper(4 * bno + 1, 4 * bno + 2);
28
        }
29

30
        if (i > 0) {
31
          int obno = (i - 1) * grid.length + j;
32
          unionHelper(4 * bno + 0, 4 * obno + 2);
33
        }
34

35
        if (j > 0) {
36
          int obno = i * grid.length + (j - 1);
37
          unionHelper(4 * bno + 3, 4 * obno + 1);
38
        }
39
      }
40
    }
41

42
    int count = 0;
43

44
    for (int i = 0; i < parent.length; i++) {
45
      if (parent[i] == i) {
46
        count++;
47
      }
48
    }
49

50
    return count;
51
  }
52

53
  public int find(int x) {
54
    if (parent[x] == x) {
55
      return parent[x];
56
    } else {
57
      parent[x] = find(parent[x]);
58
      return parent[x];
59
    }
60
  }
61

62
  public void union(int xl, int yl) {
63
    if (rank[xl] < rank[yl]) {
64
      parent[xl] = yl;
65
    } else if (rank[yl] < rank[xl]) {
66
      parent[yl] = xl;
67
    } else {
68
      parent[xl] = yl;
69
      rank[yl]++;
70
    }
71
  }
72

73
  public void unionHelper(int x, int y) {
74
    int xl = find(x);
75
    int yl = find(y);
76

77
    if (xl != yl) {
78
      union(xl, yl);
79
    }
80
  }
81
}