Python | Graph Theory  --> Union-Find algorithm | Disjoint-Set
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def regionsBySlashes(self, grid: List[str]) -> int:\n        n = len(grid)\n        p
[see the Successfully Accepted Submission](https://leetcode.com/problems/regions-cut-by-slashes/submissions/1350702325/?envType=daily-question&envId=2024-08-10)\n\n# Code\n```\nclass Solution:\n    def regionsBySlashes(self, grid: List[str]) -> int:\n        n = len(grid)\n        parent = {}\n        \n        # Initialize the union-find parent for each triangle\n        def find(x):\n            if parent[x] != x:\n                parent[x] = find(parent[x])\n            return parent[x]\n        \n        def union(x, y):\n            rootX = find(x)\n            rootY = find(y)\n            if rootX != rootY:\n                parent[rootX] = rootY\n        \n        # Each cell is represented by 4 triangles: 0 (top-left), 1 (top-right), 2 (bottom-right), 3 (bottom-left)\n        def get_index(i, j, k):\n            return (i * n + j) * 4 + k\n        \n        # Initialize all triangles\n        for i in range(n):\n            for j in range(n):\n                for k in range(4):\n                    parent[get_index(i, j, k)] = get_index(i, j, k)\n                        \n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == \'/\':\n                    union(get_index(i, j, 0), get_index(i, j, 3))\n                    union(get_index(i, j, 1), get_index(i, j, 2))\n                elif grid[i][j] == \'\\\\\':\n                    union(get_index(i, j, 0), get_index(i, j, 1))\n                    union(get_index(i, j, 2), get_index(i, j, 3))\n                else:\n                    union(get_index(i, j, 0), get_index(i, j, 1))\n                    union(get_index(i, j, 1), get_index(i, j, 2))\n                    union(get_index(i, j, 2), get_index(i, j, 3))\n                \n                # Union with right and bottom cells if possible\n                if j + 1 < n:\n                    union(get_index(i, j, 1), get_index(i, j + 1, 3))\n                if i + 1 < n:\n                    union(get_index(i, j, 2), get_index(i + 1, j, 0))\n        \n        # Count the number of distinct roots\n        return sum(find(x) == x for x in parent)\n        \n```\n\n# Regions Cut by Slashes\n\n## Key Insight\n\nEach 1x1 square can be divided into 4 smaller triangles. Depending on the character in the square:\n\n- `\'/\'` splits the square into two regions: the top-left and bottom-right triangles are connected, as are the top-right and bottom-left triangles.\n- `\'\\\\\'` splits the square similarly but in the opposite direction: the top-right and bottom-left triangles are connected, as are the top-left and bottom-right triangles.\n- `\' \'` (a blank space) leaves all four triangles connected.\n\n## Approach\n\n1. **Convert the Grid**: \n   - Imagine each 1x1 square as a 2x2 grid of triangles. \n   - Each triangle can be seen as a node in a graph, and the edges between them represent the borders of the triangles.\n\n2. **Graph Representation**: \n   - We\'ll create a graph where each triangle is a node. \n   - We\'ll connect the nodes (triangles) based on the character in the square and also connect adjacent triangles across different squares.\n\n3. **Union-Find Algorithm**: \n   - This problem can be solved using a union-find (disjoint-set) data structure. \n   - We\'ll treat each triangle as a separate component initially and then unify them based on the slashes and spaces.\n\n4. **Count the Regions**: \n   - The number of distinct components at the end gives the number of regions.\n\n## Explanation\n\n- **`get_index(i, j, k)`**: This function calculates a unique identifier for each triangle based on its position `(i, j)` and the triangle index `k` within the square.\n  \n- **Union Operations**: Depending on the character in the square, we connect (union) triangles within the square and also across adjacent squares.\n  \n- **Counting Regions**: After processing all squares, we count the number of unique components (roots) in the union-find structure, which gives the number of regions.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']