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.

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