We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Regions Cut By Slashes

Difficulty: Medium

Problem 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 '\'.

Key Insights

  • The '/' and '' characters divide the grid into regions by creating barriers.
  • Each 1 x 1 square can be represented as a node in a graph where connections (edges) exist based on the characters within the square.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to explore and count the distinct regions formed.

Space and Time Complexity

Time Complexity: O(n^2) - We visit each cell in the n x n grid once. Space Complexity: O(n^2) - The recursion stack for DFS or the queue for BFS can grow up to n^2 in the worst case.

Solution

To solve the problem, we can represent the grid as a graph where each 1 x 1 square is a node, and we traverse the grid using either depth-first search (DFS) or breadth-first search (BFS). We will mark visited nodes to ensure we count each region only once. The '/' and '' characters determine the connections between nodes, effectively allowing us to explore the entire region.

  1. Iterate through each cell in the grid.
  2. For each unvisited cell, initiate a DFS or BFS to explore all reachable cells.
  3. For each initiation of a DFS or BFS, increment the region count.
  4. Use a visited structure to keep track of which cells have already been counted.

Code Solutions

def regionsBySlashes(grid):
    n = len(grid)
    parent = {}
    
    # Helper function to find the root of a node
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    # Helper function to union two nodes
    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY
    
    # Initialize the parent mapping
    for i in range(n):
        for j in range(n):
            parent[(i, j, 0)] = (i, j, 0)  # for the top half
            parent[(i, j, 1)] = (i, j, 1)  # for the bottom half
    
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '/':
                union((i, j, 0), (i, j, 1))  # Connect top and bottom
            elif grid[i][j] == '\\':
                union((i, j, 1), (i, j, 0))  # Connect bottom and top
    
            # Connect to adjacent cells
            if i > 0:  # Connect with the cell above
                union((i, j, 0), (i - 1, j, 1))
            if j > 0:  # Connect with the cell to the left
                union((i, j, 0), (i, j - 1, 1))
    
    # Count the number of distinct roots
    regions = set()
    for key in parent:
        regions.add(find(key))
    
    return len(regions)
← Back to All Questions