Leetcode 999 Solution

This article provides solution to leetcode question 999 (regions-cut-by-slashes)
Categories:
Tags:
Access this page by simply typing in "lcs 999" in your browser address bar if you have bunnylol configured.

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)):
            regions.add(fuset.find(i))
        return len(regions)