959. Regions Cut By Slashes

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 character…


This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

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:

1

  • Input: grid = [" /","/ "]
  • Output: 2

Example 2:

2

  • Input: grid = [" /"," "]
  • Output: 1

Example 3:

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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:


This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE


Print Share Comment Cite Upload Translate Updates
APA

MD ARIFUL HAQUE | Sciencx (2024-08-10T18:48:42+00:00) 959. Regions Cut By Slashes. Retrieved from https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/

MLA
" » 959. Regions Cut By Slashes." MD ARIFUL HAQUE | Sciencx - Saturday August 10, 2024, https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/
HARVARD
MD ARIFUL HAQUE | Sciencx Saturday August 10, 2024 » 959. Regions Cut By Slashes., viewed ,<https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/>
VANCOUVER
MD ARIFUL HAQUE | Sciencx - » 959. Regions Cut By Slashes. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/
CHICAGO
" » 959. Regions Cut By Slashes." MD ARIFUL HAQUE | Sciencx - Accessed . https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/
IEEE
" » 959. Regions Cut By Slashes." MD ARIFUL HAQUE | Sciencx [Online]. Available: https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/. [Accessed: ]
rf:citation
» 959. Regions Cut By Slashes | MD ARIFUL HAQUE | Sciencx | https://www.scien.cx/2024/08/10/959-regions-cut-by-slashes/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts