# 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=["/\\", "\\/"]))
