Leetcode 999 Solution

https://leetcode.com/problems/regions-cut-by-slashes

Solution

``````class FindUnionSet:
def __init__(self, n):
self.p = list(range(n))

def find(self, i):
if self.p[i] != i:
self.p[i] = self.find(self.p[i])
return self.p[i]

def union(self, i, j):
pi = self.find(i)
pj = self.find(j)
self.p[pi] = pj

class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)

def get_index(i, j, n, direction):
if direction == 0:
return i * (n + 1) + j
elif direction == 2:
return i * (n + 1) + j + 1
elif direction == 1:
return n * (n + 1) + i * n + j
elif direction == 3:
return n * (n + 1) + (i + 1) * n + j

fuset = FindUnionSet(2 * n * (n + 1))

for i in range(n):
for j in range(n):
if grid[i][j] == ' ':
fuset.union(get_index(i, j, n, 0), get_index(i, j, n, 1))
fuset.union(get_index(i, j, n, 0), get_index(i, j, n, 2))
fuset.union(get_index(i, j, n, 0), get_index(i, j, n, 3))
elif grid[i][j] == '/':
fuset.union(get_index(i, j, n, 0), get_index(i, j, n, 1))
fuset.union(get_index(i, j, n, 2), get_index(i, j, n, 3))
elif grid[i][j] == '\\':
fuset.union(get_index(i, j, n, 0), get_index(i, j, n, 3))
fuset.union(get_index(i, j, n, 1), get_index(i, j, n, 2))

regions = set()
for i in range(2 * n * (n + 1)):