959. Regions Cut By Slashes - cocoder39/coco39_LC GitHub Wiki

959. Regions Cut By Slashes

It upscales the input grid to [m3][n3] grid then transform the problem to number of islands.

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        m = len(grid)
        n = len(grid[0])
        upscaled_grid = [[0]*n*3 for i in range(m*3)]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '/':
                    upscaled_grid[i*3][j*3+2] = 1
                    upscaled_grid[i*3+1][j*3+1] = 1
                    upscaled_grid[i*3+2][j*3] = 1
                elif grid[i][j] == '\\':
                    upscaled_grid[i*3][j*3] = 1
                    upscaled_grid[i*3+1][j*3+1] = 1
                    upscaled_grid[i*3+2][j*3+2] = 1
        
        def dfs(r, c):
            upscaled_grid[r][c] = 1
            
            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if 0 <= r+x < 3*m and 0 <= c+y < 3*n and upscaled_grid[r+x][c+y] == 0:
                    dfs(r+x, c+y)
             
        count = 0
        for i in range(m*3):
            for j in range(n*3):
                if upscaled_grid[i][j] == 0:
                    count += 1
                    dfs(i, j)
        return count