LeetCode Solutions Blog

Regions Cut By Slashes

Number: 999

Difficulty: Medium

Paid? No

Problem Description

Given an n x n grid where each cell contains either '/', '' or a blank space, the slashes partition the 1 x 1 squares into distinct regions. The goal is to count the number of separate regions formed by these partitions.

Key Insights

Each cell can be subdivided into smaller parts (e.g., 4 triangles) to model the effect of slashes and backslashes.
A '/' divides the cell from bottom-left to top-right and a '' divides from top-left to bottom-right.
Use Depth-First Search (DFS) or Union Find to group together connected sub-regions.
By connecting neighboring sub-cells (from adjacent grid cells), the entire grid forms a graph where each connected component represents a distinct region.

Space and Time Complexity

Time Complexity: O(n^2) – Each cell is processed and each sub-cell is visited at most once. Space Complexity: O(n^2) – Due to storing either an expanded grid or union structures for 4 * n^2 small regions.

Solution

We solve the problem by subdividing each 1 x 1 cell into 4 smaller regions (triangles). Label these triangles as 0, 1, 2, 3 for each cell. The connections inside the cell depend on the slash:

For a blank cell, all 4 triangles connect together.
For '/', connect triangle 0 with 3 and 1 with 2.
For '', connect triangle 0 with 1 and 2 with 3.

After making internal connections, connect adjacent cells:

Connect the bottom triangle of the current cell with the top triangle of the cell below.
Connect the right triangle with the left triangle of the adjacent cell on the right.

After constructing these connections, use DFS (or Union Find) to count the number of connected components in the entire structure. Each connected component represents a unique region.

Code Solutions

# Python solution for Regions Cut By Slashes

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        # Each cell is divided into 4 parts, total parts = 4 * n * n.
        size = n * n * 4
        # Create a list to mark visited nodes for DFS.
        visited = [False] * size
        
        # Create the adjusted grid representation
        # For a cell at (i, j), the index for a subcell k is computed as:
        # index = (i * n + j) * 4 + k
        
        # Build the graph connections using adjacency list
        graph = [[] for _ in range(size)]
        
        # Helper: Return the index given row, col and part.
        def index(i, j, k):
            return (i * n + j) * 4 + k
        
        # DS: Connect parts within the cell depending on the character.
        for i in range(n):
            for j in range(n):
                ch = grid[i][j]
                base = (i * n + j) * 4
                if ch == ' ':
                    # Connect all 4 parts together.
                    graph[base + 0].extend([base + 1, base + 2, base + 3])
                    graph[base + 1].extend([base + 0, base + 2, base + 3])
                    graph[base + 2].extend([base + 0, base + 1, base + 3])
                    graph[base + 3].extend([base + 0, base + 1, base + 2])
                elif ch == '/':
                    # Connect part 0 with 3, and part 1 with 2.
                    graph[base + 0].append(base + 3)
                    graph[base + 3].append(base + 0)
                    graph[base + 1].append(base + 2)
                    graph[base + 2].append(base + 1)
                elif ch == '\\':
                    # Connect part 0 with 1, and part 2 with 3.
                    graph[base + 0].append(base + 1)
                    graph[base + 1].append(base + 0)
                    graph[base + 2].append(base + 3)
                    graph[base + 3].append(base + 2)
        
        # Connect adjacent cells.
        for i in range(n):
            for j in range(n):
                base = (i * n + j) * 4
                # Connect bottom of cell above (if exists) with top of current cell.
                if i + 1 < n:
                    bottom_current = base + 2
                    top_below = ((i + 1) * n + j) * 4 + 0
                    graph[bottom_current].append(top_below)
                    graph[top_below].append(bottom_current)
                # Connect right of cell to left of adjacent cell.
                if j + 1 < n:
                    right_current = base + 1
                    left_adjacent = (i * n + (j + 1)) * 4 + 3
                    graph[right_current].append(left_adjacent)
                    graph[left_adjacent].append(right_current)
                # Optional: Connect top of current cell with bottom of the above cell.
                if i - 1 >= 0:
                    top_current = base + 0
                    bottom_above = ((i - 1) * n + j) * 4 + 2
                    graph[top_current].append(bottom_above)
                    graph[bottom_above].append(top_current)
                # Optional: Connect left of current cell with right of the left cell.
                if j - 1 >= 0:
                    left_current = base + 3
                    right_left = (i * n + (j - 1)) * 4 + 1
                    graph[left_current].append(right_left)
                    graph[right_left].append(left_current)
        
        # DFS to count the number of connected components.
        def dfs(node):
            stack = [node]
            while stack:
                cur = stack.pop()
                if visited[cur]:
                    continue
                visited[cur] = True
                for neighbor in graph[cur]:
                    if not visited[neighbor]:
                        stack.append(neighbor)

        components = 0
        for node in range(size):
            if not visited[node]:
                dfs(node)
                components += 1
        
        return components