leetcode - 959. Regions Cut By Slashes

Description

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a ‘/’, ‘’, or blank space ’ '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a ‘’ is represented as ‘\’.

Example 1:

Input: grid = [" /","/ "]
Output: 2

Example 2:

Input: grid = [" /","  "]
Output: 1

Example 3:

Input: grid = [“/\”,“\/”]
Output: 5
Explanation: Recall that because \ characters are escaped, “\/” refers to /, and “/\” refers to /.

Constraints:

n == grid.length == grid[i].length
1 <= n <= 30
grid[i][j] is either '/', '\', or ' '.

Solution

DFS

Solved after help.

Couldn’t just use dfs based on the original grid, because for example3 it would give 0 as the answer. And the reason for that is even the / could possibly bring regions. So we could expand the grid, or upscale the grid. The next question is, how much do we want to upscale?

The first thing would be, upscale every box to 2x2. It could solve most cases, but if we have [//,/ ], then after upscaling, the (0,2) would be considered as a single region, where actually it’s not.

So we need to upscale one more, for every box it would be a 3x3 box.

After upscaling, it’s like 200. 岛屿数量.

Time complexity: ??
Space complexity: ??

Code

DFS

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        def dfs(x: int, y: int, matrix: list) -> None:
            matrix[x][y] = 'x'
            m, n = 3 * len(grid), 3 * len(grid[0])
            for dz in (-1, 1):
                if 0 <= x + dz < m and matrix[x + dz][y] == ' ':
                    dfs(x + dz, y, matrix)
                if 0 <= y + dz < n and matrix[x][y + dz] == ' ':
                    dfs(x, y + dz, matrix)
            return
        expanded_grid = [[' '] * 3 * len(grid[0]) for _ in range(3 * len(grid))]
        # expand the grid
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '/':
                    expanded_grid[i * 3][j * 3 + 2] = '/'
                    expanded_grid[i * 3 + 1][j * 3 + 1] = '/'
                    expanded_grid[i * 3 + 2][j * 3] = '/'
                elif grid[i][j] == '\\':
                    expanded_grid[i * 3][j * 3] = '\\'
                    expanded_grid[i * 3 + 1][j * 3 + 1] = '\\'
                    expanded_grid[i * 3 + 2][j * 3 + 2] = '\\'
        res = 0
        for i in range(len(expanded_grid)):
            for j in range(len(expanded_grid[0])):
                if expanded_grid[i][j] == ' ':
                    res += 1
                    dfs(i, j, expanded_grid)
        return res