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