Regions Cut By Slashes
Medium · Graphs · Array · Union Find · Depth-First Search · Matrix
Problem
An n x n grid is made of 1 x 1 squares. Each square holds a forward slash /, a backslash, or a blank. A slash or backslash is a line from one corner of its square to the opposite corner, splitting the square into two triangles. A forward slash runs from the bottom-left corner to the top-right; a backslash from the top-left to the bottom-right.
The grid is given as grid, a list of n strings of length n. Return the number of separate regions that all the lines together divide the grid into.
In the examples and inputs, strings are written as JSON, so a backslash appears escaped: "\\" is a string holding one backslash.
Examples
Input: grid = ["/\\","\\/"] Output: 5
The four lines draw a diamond: its inside plus four corner triangles.
Input: grid = [" "," "] Output: 1
With no lines the whole grid is one region.
Input: grid = ["//","/ "] Output: 3
The slashes form two parallel diagonal lines, cutting the grid into three strips.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 30
- grid[i][j] is '/', a backslash, or ' '
Approaches
- Draw it three times larger and flood fill — time O(n²), space O(n²), nine pixels per square
Follow-up
What if a square could hold both diagonals (an X)? The four-triangle model handles it with no new cases: an X joins none of its triangles (the first use case). The 3x pixel picture handles it too, by marking both diagonals.
Related problems
Start free on Cariara · Coding problems · System design studio
