959. Regions Cut By Slashes
Medium
Topics: Array
, Hash Table
, DepthFirst Search
, BreadthFirst Search
, Union Find
, Matrix
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 '\\'
.
Example 1:
 Input: grid = [" /","/ "]
 Output: 2
Example 2:
 Input: grid = [" /"," "]
 Output: 1
Example 3:
 Input: grid = ["/\","\/"]
 Output: 5
 Explanation: Recall that because \ characters are escaped, "\/" refers to \/, and "/\" refers to /.
Constraints:
n == grid.length == grid[i].length
1 <= n <= 30

grid[i][j]
is either'/'
,'\'
, or' '
.
Solution:
We can represent each 1x1
square as 4 triangles, which allows us to apply a UnionFind (Disjoint Set Union, DSU) algorithm to count the distinct regions.
StepbyStep Approach:

Grid Representation:
 We treat each
1x1
square as 4 triangles: Topleft triangle
 Topright triangle
 Bottomleft triangle
 Bottomright triangle
 Each of these triangles is represented by an index in the UnionFind structure.
 We treat each

Mapping Characters:
 If the square is
' '
, all 4 triangles within it are connected.  If the square is
'/'
, the topleft triangle is connected to the bottomright, and the topright triangle is connected to the bottomleft.  If the square is
'\'
, the topleft triangle is connected to the topright, and the bottomleft triangle is connected to the bottomright.
 If the square is

Connecting Adjacent Cells:
 We connect the triangles of adjacent cells across the grid's boundaries. This ensures that regions spanning multiple cells are properly connected.

Counting the Regions:
 We count the number of unique sets in the UnionFind structure, which corresponds to the number of regions.
Let's implement this solution in PHP: 959. Regions Cut By Slashes
<?php
// Test cases
$grid1 = [" /", "/ "];
$grid2 = [" /", " "];
$grid3 = ["/\\", "\\/"];
echo regionsBySlashes($grid1); // Output: 2
echo regionsBySlashes($grid2); // Output: 1
echo regionsBySlashes($grid3); // Output: 5
?>
Explanation:
 The
UnionFind
class is used to manage the connected components (regions) in the grid.  For each cell in the grid, we apply the union operation based on the character (
'/'
,'\'
, or' '
).  Finally, the number of unique regions is determined by counting the distinct root parents in the UnionFind structure.
This solution efficiently handles the problem within the given constraints.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)