Problem statement

https://leetcode.com/problems/regions-cut-by-slashes/

Solution

The idea is to undestand how to create connected components. One way it to have 4 parts for each grid and then create connections, but we need to code several cases by hands. Another idea is to split each cell into 9 cells and then we can reuse problem 0200. Number of Islands.

Complexity

It is O(9n^2) for time and space.

Code

class Solution:
    def regionsBySlashes(self, grid):
        n, regions  = len(grid), 0
        g = [[0] * n * 3 for i in range(n * 3)]
        for i in range(n):
            for j in range(n):
                dr = 1 if grid[i][j] == "\\" else -1 if grid[i][j] == "/" else 0
                if dr == 0: continue
                for x in range(-1, 2):
                    g[i*3 + 1 + x][j*3 + 1 + x*dr] = 1
        
        cnt = 0
        def dfs(i, j):
            if not 0 <= i < 3*n or not 0 <= j < 3*n or g[i][j] != 0:
                return
            g[i][j] = 2
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                dfs(x, y)
        
        for i, j in product(range(3*n), range(3*n)):
            if g[i][j] == 0:
                dfs(i, j)
                cnt += 1
        
        return cnt