LeetCode 959. Regions Cut By Slashes

Post by ailswan Aug. 31, 2024

959. Regions Cut By Slashes

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

Input: grid = ["/\\","\\/"] Output: 5

Constraints: n == grid.length == grid[i].length 1 <= n <= 30 grid[i][j] is either ‘/’, ‘', or ‘ ‘.

Solution Approach

The solution transforms the grid into a larger matrix where each cell is divided into 9 smaller cells based on the slashes, and then uses DFS to count the number of connected components in the resulting matrix.

Algorithm

  1. Grid Expansion: The original grid is expanded into a larger matrix (3 times the size in both dimensions) where each cell is divided into 9 smaller cells to accommodate the slashes and their impact on the region boundaries.
  2. Slash Representation: The slashes (/ and ) are used to mark boundaries in the expanded matrix, creating barriers between different regions by setting appropriate cells to 1.
  3. DFS Traversal: A depth-first search (DFS) is performed on the expanded matrix to identify and count distinct regions by marking all connected cells starting from any unvisited cell.

Complexity

time complexity: O((3n)^2) DFS is performed on the expanded grid. In the worst case, every cell in the 3m x 3n grid could be visited once, leading to a time complexity of O((3m) * (3n)) which simplifies to O(m * n). space complexity: O((3n)^2) The space required to store the 3m x 3n grid is O((3m) * (3n)) which simplifies to O(m * n). In the worst case, the depth of the recursion could be the size of the grid, so the space required for the DFS call stack is also O(m * n).

Implement

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