959. Regions Cut By Slashes (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        m = 3 * n
        mat = [[0] * m for _ in range(m)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] == "/":
                    mat[i * 3][j * 3 + 2] = 1
                    mat[i * 3 + 1][j * 3 + 1] = 1
                    mat[i * 3 + 2][j * 3] = 1
                elif grid[i][j] == "\\":
                    mat[i * 3][j * 3] = 1
                    mat[i * 3 + 1][j * 3 + 1] = 1
                    mat[i * 3 + 2][j * 3 + 2] = 1
        def dfs(i, j):
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                x, y = i + dx, j + dy
                if (x, y) not in seen and 0 <= x < m and 0 <= y < m and mat[x][y] == 0:
                    seen.add((x, y))
                    dfs(x, y)
        seen = set()
        result = 0
        for i in range(m):
            for j in range(m):
                if mat[i][j] == 0 and (i, j) not in seen:
                    result += 1
                    dfs(i, j)
        return result