Regions Cut By Slashes
Intuition
Solution
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
# \ 1 /
# 0 2
# / 3 \
row = len(grid)
col = len(grid[0])
graph = Graph(row * col * 4)
for i in range(row):
for j in range(col):
base = (i * col + j) * 4
if grid[i][j] == ' ':
graph.add_edge(base, base + 1)
graph.add_edge(base + 1, base + 2)
graph.add_edge(base + 2, base + 3)
elif grid[i][j] == '/':
graph.add_edge(base, base + 1)
graph.add_edge(base + 2, base + 3)
else:
graph.add_edge(base, base + 3)
graph.add_edge(base + 1, base + 2)
if i > 0:
graph.add_edge(base + 1, ((i - 1) * col + j) * 4 + 3)
if i < row - 1:
graph.add_edge(base + 3, ((i + 1) * col + j) * 4 + 1)
if j > 0:
graph.add_edge(base, (i * col + j - 1) * 4 + 2)
if j < col - 1:
graph.add_edge(base + 2, (i * col + j + 1) * 4)
return ConnectedComponents(graph).count