aboutsummaryrefslogtreecommitdiff
path: root/regions_cut_by_slashes.py
blob: c25a08e4c4613635c877d75775273e627d5bc47e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 959. Regions Cut By Slashes

"""
an 'n * n' grid is composed of 1 * 1 squares where each 1 * 1 square consists
of a '/' or '\' or blank space ' '. these characters divide the square into
contiguous regions. given the grid 'grid' represented as a string array,
return the number of regions. note that backslash characters are escaped.
"""


class Solution(object):
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        n = {}

        def find(x):
            n.setdefault(x, x)
            if x != n[x]:
                n[x] = find(n[x])
            return n[x]

        def union(x, y):
            n[find(x)] = find(y)

        for i in range(len(grid)):
            for j in range(len(grid)):
                if i:
                    union((i - 1, j, 2), (i, j, 0))
                if j:
                    union((i, j - 1, 1), (i, j, 3))
                if grid[i][j] != "/":
                    union((i, j, 0), (i, j, 1))
                    union((i, j, 2), (i, j, 3))
                if grid[i][j] != "\\":
                    union((i, j, 3), (i, j, 0))
                    union((i, j, 1), (i, j, 2))
        return len(set(map(find, n)))


if __name__ == "__main__":
    obj = Solution()
    print(obj.regionsBySlashes(grid=[" /", "/ "]))
    print(obj.regionsBySlashes(grid=[" /", "  "]))
    print(obj.regionsBySlashes(grid=["/\\", "\\/"]))