<p>An <code>n x n</code> grid is composed of <code>1 x 1</code> squares where each <code>1 x 1</code> square consists of a <code>&#39;/&#39;</code>, <code>&#39;\&#39;</code>, or blank space <code>&#39; &#39;</code>. These characters divide the square into contiguous regions.</p>

<p>Given the grid <code>grid</code> represented as a string array, return <em>the number of regions</em>.</p>

<p>Note that backslash characters are escaped, so a <code>&#39;\&#39;</code> is represented as <code>&#39;\\&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/1.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [&quot; /&quot;,&quot;/ &quot;]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/2.png" style="width: 200px; height: 198px;" />
<pre>
<strong>Input:</strong> grid = [&quot; /&quot;,&quot;  &quot;]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/4.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [&quot;/\\&quot;,&quot;\\/&quot;]
<strong>Output:</strong> 5
<strong>Explanation: </strong>Recall that because \ characters are escaped, &quot;\\/&quot; refers to \/, and &quot;/\\&quot; refers to /\.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;/&#39;</code>, <code>&#39;\&#39;</code>, or <code>&#39; &#39;</code>.</li>
</ul>

from itertools import product

class UnionFind:

    def __init__(self, n) -> None:
        self.parents = list(range(n))
        self.weights = [1] * n

    def find(self, pt_id):
        if pt_id >= len(self.parents):
            return
        parent = self.parents[pt_id]
        if parent == pt_id:
            return parent
        parent = self.find(parent)
        self.parents[pt_id] = parent
        return parent
    
    def union(self, a, b):
        parent_a = self.find(a)
        parent_b = self.find(b)
        if parent_a == parent_b:
            return
        if self.weights[parent_a] > self.weights[parent_b]:
            self.parents[parent_b] = parent_a
            self.weights[parent_a] += self.weights[b]
        else:
            self.parents[parent_a] = parent_b
            self.weights[parent_b] += self.weights[a]


class Solution:

    def get_pt_id(self, pt):
        y, x = pt
        return y * self.graph_edge_size + x
    
    def is_out_of_bounds(self, value):
        return value < 0 or value >= self.graph_edge_size

    def regionsBySlashes(self, grid):
        graph = self.build_graph(grid)
        uf = UnionFind(self.graph_edge_size ** 2)
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for y, x in product(range(self.graph_edge_size), range(self.graph_edge_size)):
            value = graph[y][x]
            if value:
                continue

            for dir in dirs:
                dx, dy = dir
                new_x = x + dx
                new_y = y + dy
                if self.is_out_of_bounds(new_x) or self.is_out_of_bounds(new_y):
                    continue
                new_value = graph[new_y][new_x]
                if new_value:
                    continue
                uf.union(self.get_pt_id((x, y)), self.get_pt_id((new_x, new_y)))

        unique_groups = set()
        for y, row in enumerate(graph):
            for x, value in enumerate(row):
                pt_id = self.get_pt_id((x, y))
                if not value:
                    unique_groups.add(uf.find(pt_id))

        return len(unique_groups)

    def build_graph(self, grid):
        n = len(grid)
        graph_edge_size = 3 * n + 1
        self.graph_edge_size = graph_edge_size
        graphs = [None] * graph_edge_size
        for i in range(graph_edge_size):
            graphs[i] = [0] * graph_edge_size
        for row in range(n):
            for col in range(n):
                connected_nodes = self.get_connected_nodes(grid, (col, row))
                if not connected_nodes:
                    continue

                for x, y in connected_nodes:
                    graphs[y][x] = 1
        # pprint_graph(graphs)
        return graphs

    def get_connected_nodes(self, grid, point):
        connecting_directions = {
            "/": [(3, 0), (2, 1), (1, 2), (0, 3)],
            "\\": [(0, 0), (1, 1), (2, 2), (3, 3)]
        }

        x, y = point
        symbol = grid[y][x]
        connecting_dirs = connecting_directions.get(symbol)
        if not connecting_dirs:
            return None

        for dx, dy in connecting_dirs:
            yield 3 * x + dx, 3 * y + dy
17233