Regions Cut by Slashes

Count connected regions in an N x N grid of '/' and '\\' characters.

grid dfs union-find strings

An n x n grid is composed of 1 x 1 squares where each square contains either a forward slash ('/'), a backslash ('\\'), or a blank space (' '). These characters divide the square into regions. Slashes and backslashes act as walls that partition the square into triangles or leave it as one region if blank.

Regions are connected if they share an edge (not just a point). The outer boundary of the grid also acts as walls, so the area outside the grid is not considered a region.

Your task is to implement the function `regions_by_slashes(grid)` that takes a list of strings, each of length n, representing the grid, and returns the number of regions.

For example, a single square '/' divides the square into two regions: the triangle above-left and the triangle below-right. They touch only at the center point, so they are not connected. Thus, the answer for ['/'] is 2.

**Input:**
- `grid`: List[str] with n rows, each string of length n (n >= 1). Characters are limited to '/', '\\', and ' '.

**Output:**
- int: the count of connected regions.

**Constraints:**
- 1 <= n <= 30
- The grid contains only '/', '\\', and spaces.
- Time complexity: O(n^2) expected, O(n^2 α(n)) with union-find, O(n^2) with DFS on expanded grid. Space: O(n^2).

Constraints

1 <= n <= 30. The grid contains only '/', '\\', and spaces. Time complexity: O(n^2) expected, O(n^2 α(n)) with union-find, O(n^2) with DFS on expanded grid. Space: O(n^2).

Example

>>> regions_by_slashes([" /", "/ "])  # note: strings are length 2: [' /', '/ ']
2
>>> regions_by_slashes([" /", "  "])
1
>>> regions_by_slashes(["/\\", "\\/"])
5
>>> regions_by_slashes(["//", "/ "])
3

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Scale up each cell into a 3x3 subgrid and fill cells where the slash passes.

Use DFS or BFS to count connected components of empty cells.

Ever wondered how a backslash looks? In Python strings, backslash is escaped as '\\'. In the grid, it's a single backslash character.

Think of the grid borders as walls; only empty sub-cells inside the scaled grid count as traversable space.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.