959. Regions Cut By Slashes

[mah-shamim]

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

[mah-shamim]

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
class UnionFind {
    private $parent;
    
    public function __construct($n) {
        $this->parent = range(0, $n - 1);
    }
    
    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }
    
    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX != $rootY) {
            $this->parent[$rootX] = $rootY;
        }
    }
}

function regionsBySlashes($grid) {
    $n = count($grid);
    $uf = new UnionFind($n * $n * 4);
    
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $root = 4 * ($i * $n + $j);
            $char = $grid[$i][$j];
            
            // Connect the parts within the cell
            if ($char == ' ') {
                $uf->union($root, $root + 1);
                $uf->union($root + 1, $root + 2);
                $uf->union($root + 2, $root + 3);
            } elseif ($char == '/') {
                $uf->union($root, $root + 3);
                $uf->union($root + 1, $root + 2);
            } elseif ($char == '\\') {
                $uf->union($root, $root + 1);
                $uf->union($root + 2, $root + 3);
            }
            
            // Connect with the right cell
            if ($j + 1 < $n) {
                $uf->union($root + 1, 4 * ($i * $n + $j + 1) + 3);
            }
            // Connect with the bottom cell
            if ($i + 1 < $n) {
                $uf->union($root + 2, 4 * (($i + 1) * $n + $j));
            }
        }
    }
    
    $regions = 0;
    for ($i = 0; $i < $n * $n * 4; $i++) {
        if ($uf->find($i) == $i) {
            $regions++;
        }
    }
    
    return $regions;
}

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