We need to count the connected components in the undirected grid graph. Since putting “/” in a cell divides the cell into two not-connected regions: [ / ], we shall consider each cell having left and right halves. We treat ” ” like “/”, only difference is for ” ” the two halves of the same cell are also connected. Thus, effectively, each cell can have either “/” or “\”.
So, for the 
Time: 
class UnionFind:
def __init__(self, n):
self.n = n
self.parent_of, self.rank_of = {}, {}
self.grid = {}
self.cc_count = 0
def __neibors_of_left(self, row, col, char):
neibors = []
if char in "/ ":
# top
if row-1 >= 0 and (row-1, col) in self.grid:
top_char = self.grid[(row-1, col)]
if top_char in "/ ":
neibors.append( (row-1, col, 1) )
else:
neibors.append( (row-1, col, 0) )
else:
# down
if row+1 < self.n and (row+1, col) in self.grid:
down_char = self.grid[(row+1, col)]
if down_char in "/ ":
neibors.append( (row+1, col, 0) )
else:
neibors.append( (row+1, col, 1) )
# left
if col-1 >= 0 and (row, col-1) in self.grid:
neibors.append( (row, col-1, 1) )
# right
if char == " ":
neibors.append( (row, col, 1) )
return neibors
def __neibors_of_right(self, row, col, char):
neibors = []
if char in "/ ":
# down
if row+1 < self.n and (row+1, col) in self.grid:
down_char = self.grid[(row+1, col)]
if down_char in "/ ":
neibors.append( (row+1, col, 0) )
else:
neibors.append( (row+1, col, 1) )
else:
# top
if row-1 >= 0 and (row-1, col) in self.grid:
top_char = self.grid[(row-1, col)]
if top_char in "/ ":
neibors.append( (row-1, col, 1) )
else:
neibors.append( (row-1, col, 0) )
# right
if col+1 < self.n and (row, col+1) in self.grid:
neibors.append( (row, col+1, 0) )
return neibors
def __compress_path(self, u, root):
while u != (p := self.parent_of[u]):
self.parent_of[u] = root
u = p
def __find(self, u):
root = u
while root != (p := self.parent_of[root]):
root = p
self.__compress_path(u, root)
return root
def __union(self, u, v):
root_u = self.__find(u)
root_v = self.__find(v)
if root_u == root_v:
return
self.cc_count -= 1
rank_u = self.rank_of[root_u]
rank_v = self.rank_of[root_v]
if rank_u == rank_v:
self.parent_of[root_u] = root_v
self.rank_of[root_v] += 1
return
if rank_u < rank_v:
self.parent_of[root_u] = root_v
else:
self.parent_of[root_v] = root_u
def add(self, row, col, char):
self.grid[(row, col)] = char
u_left, u_right = (row, col, 0), (row, col, 1)
self.parent_of[u_left] = u_left
self.rank_of[u_left] = 0
self.parent_of[u_right] = u_right
self.rank_of[u_right] = 0
self.cc_count += 2
for v in self.__neibors_of_left(row, col, char):
self.__union(u_left, v)
for v in self.__neibors_of_right(row, col, char):
self.__union(u_right, v)
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
uf = UnionFind(len(grid))
for row, row_str in enumerate(grid):
for col, char in enumerate(row_str):
uf.add(row, col, char)
return uf.cc_count
unreasonably effective 
Leave a comment