Regions Cut By Slashes

Regions Cut By Slashes medium

Description

An n × n grid is composed of 1 × 1 squares where each 1 × 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.

Examples

> Case 1:
    grid = [" /", "/ "]
    Output: 2
 
> Case 2:
    grid = [" /", "  "]
    Output: 1
 
> Case 3:
    grid = ["/\\", "\\/"]
    Output: 5

Constraints

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

State design

The classic encoding: split each cell into 4 triangles — top (0), right (1), bottom (2), left (3).

   ____
  |\  /|
  | \/ |    0 = top
  | /\ |    1 = right
  |/  \|    2 = bottom
   ‾‾‾‾     3 = left

Now apply rules inside each cell:

Blank space — all 4 triangles are in the same region: union(0,1), union(1,2), union(2,3).
/ — separates the cell into {top, left} and {right, bottom}: union(0,3), union(1,2).
\\ — separates into {top, right} and {bottom, left}: union(0,1), union(2,3).

Then handle inter-cell connections:

Cell’s right triangle (1) connects to right neighbor’s left triangle (3).
Cell’s bottom triangle (2) connects to bottom neighbor’s top triangle (0).

Final answer: the DSU’s component count.

Triangle index for cell (r, c) triangle t: 4 * (r * n + c) + t.

Try it yourself

⌨ Regions Cut By Slashes — return the region count

def regions_by_slashes(grid):
  # split each cell into 4 triangles (top/right/bottom/left), union per the slash, then count
  pass

Hint

Index triangle t of cell (r, c) as 4*(r*n + c) + t with 0=top, 1=right, 2=bottom, 3=left. Union the triangles inside each cell per its character, then union each cell's right(1) to the neighbor's left(3) and bottom(2) to the lower neighbor's top(0). Answer is the component count.

Reveal solution

Code

Analysis

Time: O(n² · α(n²)) — every cell does a constant number of unions.
Space: O(n²) for the DSU.

The “split each cell into pieces” technique generalizes. When the geometry doesn’t fit cell-on-cell DSU (e.g. slashes cut cells; brick walls split horizontally), subdivide. Two triangles, four triangles, even nine sub-cells. Once the units are right, plain DSU does the rest.

Same skin

Number of Islands — single-cell DSU on a grid.
Number of Closed Islands — grid DSU with boundary handling.
Max Area of Island — grid DSU with size tracking.

Smallest String With Swaps Evaluate Division

Finished this page?