Solution: Regions Cut by Slashes
Statement▼
An n×n grid is composed of n, 1×1 squares, where each 1×1 square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.
Given the grid represented as a string array, return the number of regions.
Note:
- Backslash characters are escaped, so “\” is represented as “\\”.
- A 1×1 square in the grid will be referred to as a box.
Constraints:
- The grid consists of only “/”, “\”, or " " characters.
- 1 ≤
grid.length≤ 30
The following demonstration shows how the grid can be visualized:
Solution
We can combine the smaller regions (represented by 1x1 boxes) into bigger ones to make it easier to determine the count of distinct regions overall. For this, we first divide each 1x1 box into four parts. Then, we start traversing the grid, visiting each box, and see what parts of each box can be merged. This is decided by the character which corresponds to a particular box. If it’s a "/" or a "\", out of the four parts, we merge the two parts above the slash into the same for the two parts below the slash. This results in a box now having only two regions overall (one above the slash and the other below the slash). However, if the character corresponding to the box is " ", we merge all four parts. To achieve this, we use the union find pattern. Merging is done using the union method. It keeps on merging the regions into connected components. Once all the boxes are processed, we return the number of distinct connected components representing the number of regions cut by slashes.
Here’s how the algorithm works:
We create a
parentarray containing4×n×n elements where each element equals its corresponding index.Every four consecutive elements in this array represent a
1×1 box in the grid.We associate each
...
Solution: Regions Cut by Slashes
Statement▼
An n×n grid is composed of n, 1×1 squares, where each 1×1 square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.
Given the grid represented as a string array, return the number of regions.
Note:
- Backslash characters are escaped, so “\” is represented as “\\”.
- A 1×1 square in the grid will be referred to as a box.
Constraints:
- The grid consists of only “/”, “\”, or " " characters.
- 1 ≤
grid.length≤ 30
The following demonstration shows how the grid can be visualized:
Solution
We can combine the smaller regions (represented by 1x1 boxes) into bigger ones to make it easier to determine the count of distinct regions overall. For this, we first divide each 1x1 box into four parts. Then, we start traversing the grid, visiting each box, and see what parts of each box can be merged. This is decided by the character which corresponds to a particular box. If it’s a "/" or a "\", out of the four parts, we merge the two parts above the slash into the same for the two parts below the slash. This results in a box now having only two regions overall (one above the slash and the other below the slash). However, if the character corresponding to the box is " ", we merge all four parts. To achieve this, we use the union find pattern. Merging is done using the union method. It keeps on merging the regions into connected components. Once all the boxes are processed, we return the number of distinct connected components representing the number of regions cut by slashes.
Here’s how the algorithm works:
We create a
parentarray containing4×n×n elements where each element equals its corresponding index.Every four consecutive elements in this array represent a
1×1 box in the grid.We associate each
...