959.md

959. Regions Cut By Slashes

Solution 1 (time O(n^2), space O(n^2))

# DFS
class Solution(object):
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        n = len(grid)
        new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * n)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] == "/":
                    new_grid[i * 3 + 2][j * 3] = 1
                    new_grid[i * 3 + 1][j * 3 + 1] = 1
                    new_grid[i * 3][j * 3 + 2] = 1
                elif grid[i][j] == "\\":
                    new_grid[i * 3][j * 3] = 1
                    new_grid[i * 3 + 1][j * 3 + 1] = 1
                    new_grid[i * 3 + 2][j * 3 + 2] = 1
        
        def dfs(i, j):
            new_grid[i][j] = 1
            if i - 1 >= 0 and new_grid[i - 1][j] == 0:
                dfs(i - 1, j)
            if i + 1 < 3 * n and new_grid[i + 1][j] == 0:
                dfs(i + 1, j)
            if j - 1 >= 0 and new_grid[i][j - 1] == 0:
                dfs(i, j - 1)
            if j + 1 < 3 * n and new_grid[i][j + 1] == 0:
                dfs(i, j + 1)

        ans = 0
        for i in range(3 * n):
            for j in range(3 * n):
                if new_grid[i][j] == 0:
                    ans += 1
                    dfs(i, j)
        return ans