Regions Cut By Slashes - Practice Coding Problems

Regions Cut By Slashes - Problem

Array Hash Table Depth-First Search Breadth-First Search Union Find Matrix Medium

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

Input & Output

Example 1 — Basic Slash Division

$ Input: grid = [" /","/ "]

› Output: 2

💡 Note: The 2x2 grid has a '/' in positions (0,1) and (1,0). These slashes divide the grid into 2 separate regions: one triangle-shaped region in the top-left and bottom-right corners, and another in the top-right and bottom-left corners.

Example 2 — Backslash Division

$ Input: grid = [" \\","\\ "]

› Output: 2

💡 Note: The backslashes create a different pattern than forward slashes, but still divide the 2x2 grid into 2 regions. The backslashes connect opposite corners, creating 2 triangle-shaped regions.

Example 3 — No Division

$ Input: grid = [" "," "]

› Output: 1

💡 Note: All cells are empty spaces, so there are no barriers dividing the grid. The entire 2x2 area forms one single connected region.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2×2 grid with forward slashes: [" /", "/ "]

Slash Barriers

Slashes act as barriers dividing the space

Count Regions

Result: 2 separate triangular regions

Key Takeaway

🎯 Key Insight: Scale up the grid 3x to clearly visualize how slashes divide regions

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is to scale up each 1×1 cell to a 3×3 grid where slashes become clear barrier patterns. Use DFS on the scaled grid to count connected regions. Best approach is 3x Grid Scaling with DFS. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ 3x Grid Scaling with DFS	O(n²)	O(n²)	Scale each cell to 3x3 to visualize slash divisions clearly
Brute Force DFS	O(n²)	O(n²)	Try DFS from every unvisited position in original grid

3x Grid Scaling with DFS — Algorithm Steps

Step 1: Scale grid from n×n to 3n×3n
Step 2: Draw slash patterns in each 3×3 cell
Step 3: DFS to count connected empty regions

Visualization

Tap to expand

Step-by-Step Walkthrough

Scale Up

Transform 2x2 grid to 6x6 with slash patterns

Draw Slashes

Mark diagonal barrier patterns in scaled grid

Count Regions

DFS finds 2 connected regions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int scaled[150][150];
int n;

void dfs(int x, int y) {
    if (x < 0 || x >= 3*n || y < 0 || y >= 3*n || scaled[x][y] == 1) {
        return;
    }
    scaled[x][y] = 1; // Mark as visited
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
}

int solution(char grid[][51], int size) {
    n = size;
    // Initialize scaled grid
    memset(scaled, 0, sizeof(scaled));
    
    // Fill the scaled grid
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '/') {
                // Draw diagonal from bottom-left to top-right
                scaled[3*i][3*j+2] = 1;
                scaled[3*i+1][3*j+1] = 1;
                scaled[3*i+2][3*j] = 1;
            } else if (grid[i][j] == '\\') {
                // Draw diagonal from top-left to bottom-right
                scaled[3*i][3*j] = 1;
                scaled[3*i+1][3*j+1] = 1;
                scaled[3*i+2][3*j+2] = 1;
            }
        }
    }
    
    // DFS to count regions
    int regions = 0;
    for (int i = 0; i < 3 * n; i++) {
        for (int j = 0; j < 3 * n; j++) {
            if (scaled[i][j] == 0) {
                dfs(i, j);
                regions++;
            }
        }
    }
    
    return regions;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char grid[51][51];
    int size = 0;
    
    // Simple parsing - extract strings from JSON array
    char *token = strtok(line, "[]\",");
    while (token != NULL && size < 51) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            strcpy(grid[size], token);
            size++;
        }
        token = strtok(NULL, "[]\",");
    }
    
    printf("%d\n", solution(grid, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Visit each cell in 3n×3n scaled grid once during DFS

⚠ Quadratic Growth

Space Complexity

O(n²)

3n×3n scaled grid plus DFS recursion stack

⚠ Quadratic Space

52.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

3x Grid Scaling with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler