959. Regions Cut By Slashes
Medium
Topics: Array
, Hash Table
, Depth-First Search
, Breadth-First 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 Union-Find (Disjoint Set Union, DSU) algorithm to count the distinct regions.
Step-by-Step Approach:
-
Grid Representation:
- We treat each
1x1
square as 4 triangles:- Top-left triangle
- Top-right triangle
- Bottom-left triangle
- Bottom-right triangle
- Each of these triangles is represented by an index in the Union-Find structure.
- We treat each
-
Mapping Characters:
- If the square is
' '
, all 4 triangles within it are connected. - If the square is
'/'
, the top-left triangle is connected to the bottom-right, and the top-right triangle is connected to the bottom-left. - If the square is
'\'
, the top-left triangle is connected to the top-right, and the bottom-left triangle is connected to the bottom-right.
- 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 Union-Find 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 Union-Find 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)