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

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        """
        approach 1
        we can represent each 1x1 grid as a 3x3 matrix and represent the slashes as boundaries represented by 1
        rest of the region is 0
        from there, we can do a bfs on each region that starts with 0 and fill them up with 1 as we go
        by the end we will have the total number of regions

        approach 2
        we can represent each 1x1 grid as 4 triangles made by splitting it across both diagonals
        can represent the triangle as 0, 1, 2, 3 clockwise
        we know given a grid, the top triangle of a grid and bottom triangle of the grid on top will always be one connected component
        we also know if a grid has / , triangles 0 3 and 1 2 will be one connected component

        we can connect all of these disjoint components using disjoint set union
        for each triangle, give it a parent
        as we're combining the regions into one component, we can update parent of the combined component to the same parent

        we start off by having n*n*4 regions
        as we start processing the regions and combining them, we can subtract from 

        """
        n = len(grid)
        total_regions = n * n * 4
        parent_array = [-1] * (n * n * 4)

        def triangle_index(r , c, i):
            return (n*r + c) * 4 + i

        def find_parent(triangle):
            if parent_array[triangle] == -1:
                return triangle
            
            return find_parent(parent_array[triangle])

        def dsu(triangle1, triangle2):
            parent1 = find_parent(triangle1)
            parent2 = find_parent(triangle2)
            if parent1 == parent2:
                return 0
            parent_array[parent1] = parent2
            return 1

        # loop through the grid and process the regions as we come across / or \\
        for r in range(n):
            for c in range(n):
                # handles case where top and bottom triangles are connected
                if r > 0:
                    # disjoint set union combine regions
                    total_regions -= dsu(triangle_index(r, c, 0), triangle_index(r-1, c, 2))
                if c > 0:
                    total_regions -= dsu(triangle_index(r, c-1, 1), triangle_index(r, c, 3))
                if grid[r][c] == '/':
                    # disjoint set union combine regions
                    total_regions -= dsu(triangle_index(r, c, 0), triangle_index(r, c, 3))
                    total_regions -= dsu(triangle_index(r, c, 1), triangle_index(r, c, 2))
                if grid[r][c] == '\\':
                    # disjoint set union combine regions
                    total_regions -= dsu(triangle_index(r, c, 2), triangle_index(r, c, 3))
                    total_regions -= dsu(triangle_index(r, c, 0), triangle_index(r, c, 1))
                if grid[r][c] == ' ':
                    total_regions -= dsu(triangle_index(r, c, 0), triangle_index(r, c, 3))
                    total_regions -= dsu(triangle_index(r, c, 1), triangle_index(r, c, 2))
                    total_regions -= dsu(triangle_index(r, c, 2), triangle_index(r, c, 3))
                    total_regions -= dsu(triangle_index(r, c, 0), triangle_index(r, c, 1))
        print(parent_array)

        return total_regions













        # n = len(grid)
        # total_triangles = n*n*4
        # parent_array = [-1] * total_triangles

        # total_regions = total_triangles
        
        # # index of a triangle in the flattened parent array
        # # each cell divided into 4 triangles, numbered 0 to 3 clockwise from the top
        # def _get_triangle_index(row, col, triangle_index):
        #     return (n*row + col)*4 + triangle_index

        # def _find_parent(triangle):
        #     if parent_array[triangle] == -1:
        #         return triangle
        #     parent_array[triangle] = _find_parent(parent_array[triangle])
        #     return parent_array[triangle]

        # def _union_triangles(triangle_1, triangle_2):
        #     parent_1 = _find_parent(triangle_1)
        #     parent_2 = _find_parent(triangle_2)
        #     if parent_1 != parent_2:
        #         parent_array[parent_1] = parent_2
        #         return 1
        #     return 0

        # for r in range(n):
        #     for c in range(n):
        #         if r > 0:
        #             total_regions -= _union_triangles(_get_triangle_index(r, c, 0), _get_triangle_index(r-1, c, 2))
        #         if c > 0:
        #             total_regions -= _union_triangles(_get_triangle_index(r, c-1, 1), _get_triangle_index(r, c, 3))
        #         if grid[r][c] != '/':
        #             total_regions -= _union_triangles(_get_triangle_index(r, c, 0), _get_triangle_index(r, c, 1))
        #             total_regions -= _union_triangles(_get_triangle_index(r, c, 2), _get_triangle_index(r, c, 3))
        #         if grid[r][c] != '\\':
        #             total_regions -= _union_triangles(_get_triangle_index(r, c, 0), _get_triangle_index(r, c, 3))
        #             total_regions -= _union_triangles(_get_triangle_index(r, c, 2), _get_triangle_index(r, c, 1))

        # return total_regions

        """
        approach 1 num islands

        from collections import deque
        n = len(grid)
        matrix = []
        for i in range(n*3):
            matrix.append([0] * (n*3))

        for i in range(n):
            for j in range(n):
                base_row = i * 3
                base_col = j * 3
                if grid[i][j] == '/':
                    matrix[base_row][base_col+2] = 1
                    matrix[base_row+1][base_col+1] = 1
                    matrix[base_row+2][base_col] = 1
                elif grid[i][j] == '\\':
                    matrix[base_row][base_col] = 1
                    matrix[base_row+1][base_col+1] = 1
                    matrix[base_row+2][base_col+2] = 1

        num_regions = 0
        q = deque()
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                if matrix[i][j] == 0:
                    num_regions += 1
                    q.append((i, j))
                    while q:
                        r, c = q.popleft()
                        neighbors = [(r+1, c), (r-1, c), (r, c-1), (r, c+1)]
                        for n_r, n_c in neighbors:
                            if 0 <= n_r < len(matrix) and 0 <= n_c < len(matrix):
                                if matrix[n_r][n_c] != 1:
                                    matrix[n_r][n_c] = 1 
                                    q.append((n_r, n_c))
        return num_regions

        """
20169