1
# Runtime: 124 ms (Top 90.60%) | Memory: 14.5 MB (Top 61.93%)
2
class Solution:
3
    def regionsBySlashes(self, grid: List[str]) -> int:
4
        n = len(grid)
5
        dots = n + 1
6
        par = [0] * (dots * dots)
7
        rank = [0] * (dots * dots)
8
        self.count = 1
9

10
        def find(x):
11
            if par[x] == x:
12
                return x
13
            temp = find(par[x])
14
            par[x] = temp
15
            return temp
16

17
        def union(x, y):
18
            lx = find(x)
19
            ly = find(y)
20
            if lx != ly:
21
                if rank[lx] > rank[ly]:
22
                    par[ly] = lx
23
                elif rank[lx] < rank[ly]:
24
                    par[lx] = ly
25
                else:
26
                    par[lx] = ly
27
                    rank[ly] += 1
28
            else:
29
                self.count += 1
30

31
        # -------------------------------------------#
32
        for i in range(len(par)):
33
            par[i] = i
34
            rank[i] = 1
35
        for i in range(dots):
36
            for j in range(dots):
37
                if i == 0 or j == 0 or i == dots - 1 or j == dots - 1:
38
                    cellno = i * dots + j
39
                    if cellno != 0:
40
                        union(0, cellno)
41
        for i in range(len(grid)):
42
            ch = grid[i]
43
            for j in range(len(ch)):
44
                if ch[j] == "/":
45
                    cellno1 = i * dots + j + 1
46
                    cellno2 = (i + 1) * dots + j
47

48
                    union(cellno1, cellno2)
49
                elif ch[j] == "\\":
50
                    cellno1 = i * dots + j
51
                    cellno2 = (i + 1) * dots + j + 1
52
                    union(cellno1, cellno2)
53
        return self.count