💢☠💫Easiest👾Faster✅💯 Lesser🧠 🎯 C++✅Python3🐍✅Java✅C✅Python🐍✅C#✅💥🔥💫Explained☠💥🔥 Beats 💯
Intuition\n\n\n\n\n\n Describe your first thoughts on how to solve this problem. \nC++ []\nclass Solution {\n\n    vector<int> parent;\n\n    int getParent(int 
# Intuition\n![0ehh83fsnh811.jpg](https://assets.leetcode.com/users/images/f6e76ec1-28c1-406d-9ef3-62410993be77_1723316274.750548.jpeg)\n![Screenshot 2024-08-11 000728.png](https://assets.leetcode.com/users/images/47d459ee-8801-47ba-a38c-b73e4362d316_1723316294.0639281.png)\n![Screenshot 2024-08-11 001749.png](https://assets.leetcode.com/users/images/84ca1dd4-3155-437e-8147-0dc6604787b2_1723316302.0643005.png)\n![Screenshot 2024-08-11 002415.png](https://assets.leetcode.com/users/images/528ac642-28da-41e5-8415-edb5e5f967a2_1723316309.506285.png)\n![Screenshot 2024-08-11 002432.png](https://assets.leetcode.com/users/images/535f6d1c-f1ab-4b2a-9076-6b474a0a2551_1723316434.3609486.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\n```C++ []\nclass Solution {\n\n    vector<int> parent;\n\n    int getParent(int node) {\n        if (parent[node] == node) {\n            return node;\n        }\n\n        return parent[node] = getParent(parent[node]);\n    }\n\n    void unionSet(int a, int b) {\n        int parentA = getParent(a);\n        int parentB = getParent(b);\n\n        if (parentA == parentB) {\n            return;\n        }\n\n        parent[parentB] = parentA;\n    }\n\npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size();\n        if (n == 0) {\n            return 0;\n        }\n        int m = grid[0].size();\n        parent = vector<int>((n + 1) * (m + 1) + 1);\n        for (int i = 0; i < parent.size(); i++) {\n            parent[i] = i;\n        }\n\n        for (int i = 0; i < n; i++) {\n            int a = i * (m + 1);\n            int b = (i + 1) * (m + 1);\n            unionSet(a, b);\n\n            a = i * (m + 1) + m;\n            b = (i + 1) * (m + 1) + m;\n            unionSet(a, b);\n        }\n\n        for (int j = 0; j < m; j++) {\n            int a = j;\n            int b = j + 1;\n            unionSet(a, b);\n\n            a = (n) * (m + 1) + j;\n            b = (n) * (m + 1) + j + 1;\n            unionSet(a, b);\n        }\n\n        int cnt = 1;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                int end1;\n                int end2;\n                if (grid[i][j] == \'/\') {\n                    // connect (i, j+1) and (i+1, j)\n                    end1 = i * (m + 1) + j + 1;\n                    end2 = (i + 1) * (m + 1) + j;\n                } else if (grid[i][j] == \'\\\\\') {\n                    // connect (i, j) and (i+1, j+1)\n                    end1 = i * (m + 1) + j;\n                    end2 = (i + 1) * (m + 1) + j + 1;\n                } else {\n                    continue;\n                }\n                int parentA = getParent(end1);\n                int parentB = getParent(end2);\n                if (parentA == parentB) {\n                    cnt++;\n                } else {\n                    parent[parentB] = parentA;\n                }\n            }\n        }\n\n        return cnt;\n    }\n};\n```\n```python3 []\nclass Solution:\n    def regionsBySlashes(self, grid: List[str]) -> int:\n        n = len(grid)\n        # Create a union-find structure with 4 times the number of triangles\n        # Each cell has 4 triangles: top-left, top-right, bottom-left, bottom-right\n        parent = [-1] * (4 * n * n)\n        \n        def find(x):\n            if parent[x] == -1:\n                return x\n            else:\n                root = find(parent[x])\n                parent[x] = root  # path compression\n                return root\n        \n        def union(x, y):\n            rootX = find(x)\n            rootY = find(y)\n            if rootX != rootY:\n                parent[rootY] = rootX\n        \n        # Initialize parent pointers\n        for i in range(n):\n            for j in range(n):\n                base = 4 * (i * n + j)\n                if grid[i][j] == \' \':\n                    union(base, base + 1)\n                    union(base + 1, base + 2)\n                    union(base + 2, base + 3)\n                elif grid[i][j] == \'/\':\n                    union(base, base + 3)\n                    union(base + 1, base + 2)\n                elif grid[i][j] == \'\\\\\':\n                    union(base, base + 1)\n                    union(base + 2, base + 3)\n                \n                # Connect adjacent cells\n                if j < n - 1:\n                    union(base + 1, 4 * (i * n + j + 1) + 3)  # right of current cell\n                if i < n - 1:\n                    union(base + 2, 4 * ((i + 1) * n + j))  # below current cell\n        \n        # Count distinct regions\n        count = 0\n        for i in range(4 * n * n):\n            if parent[i] == -1:\n                count += 1\n        \n        return count\n\n```\n```Java []\nclass Solution {\n    int[] parent;\n    int[] rank;\n    int count;\n\n    public int regionsBySlashes(String[] grid) {\n        int rows = grid.length;\n        int dots = rows + 1;\n        parent = new int[dots * dots];\n        rank = new int[dots * dots];\n        for (int i = 0; i < parent.length; i++) {\n            parent[i] = i;\n            rank[i] = 1;\n        }\n\n        for (int i = 0; i < dots; i++) {\n            for (int j = 0; j < dots; j++) {\n                if (i == 0 || j == 0 || i == rows || j == rows) {\n                    int cells = i * dots + j;\n                    union(0, cells);\n                }\n            }\n        }\n\n        for (int i = 0; i < rows; i++) {\n            char[] ch = grid[i].toCharArray();\n            for (int j = 0; j < ch.length; j++) {\n                if (ch[j] == \'\\\\\') {\n                    int cell1 = i * dots + j;\n                    int cell2 = (i + 1) * dots + (j + 1);\n                    union(cell1, cell2);\n                } else if (ch[j] == \'/\') {\n                    int cell1 = (i + 1) * dots + j;\n                    int cell2 = i * dots + (j + 1);\n                    union(cell1, cell2);\n                }\n            }\n        }\n        return count;\n    }\n\n    public void union(int a, int b) {\n        int parentA = find(a);\n        int parentB = find(b);\n        if (parentA == parentB) {\n            count++;\n        } else {\n            if (rank[parentA] > rank[parentB]) {\n                parent[parentB] = parentA;\n            } else if (rank[parentA] < rank[parentB]) {\n                parent[parentA] = parentB;\n            } else {\n                parent[parentB] = parentA;\n                rank[parentA]++;\n            }\n        }\n    }\n\n    public int find(int a) {\n        if (parent[a] == a)\n            return a;\n        int temp = find(parent[a]);\n        parent[a] = temp;\n        return temp;\n    }\n\n}\n```\n```Python []\nclass Solution:\n    def __init__(self):\n        self.parent = []\n        self.rank = []\n        self.count = 0\n\n    def regionsBySlashes(self, grid):\n        n = len(grid)\n        dots = n + 1\n        self.parent = [i for i in range(dots * dots)]\n        self.rank = [1] * (dots * dots)\n\n        # Connect boundaries to the top-left corner (0,0)\n        for i in range(dots):\n            for j in range(dots):\n                if i == 0 or j == 0 or i == n or j == n:\n                    cell = i * dots + j\n                    self.union(0, cell)\n\n        # Process each cell and connect regions based on slashes\n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == \'\\\\\':\n                    cell1 = i * dots + j\n                    cell2 = (i + 1) * dots + (j + 1)\n                    self.union(cell1, cell2)\n                elif grid[i][j] == \'/\':\n                    cell1 = (i + 1) * dots + j\n                    cell2 = i * dots + (j + 1)\n                    self.union(cell1, cell2)\n\n        return self.count\n\n    def union(self, a, b):\n        parentA = self.find(a)\n        parentB = self.find(b)\n        if parentA == parentB:\n            self.count += 1\n        else:\n            if self.rank[parentA] > self.rank[parentB]:\n                self.parent[parentB] = parentA\n            elif self.rank[parentA] < self.rank[parentB]:\n                self.parent[parentA] = parentB\n            else:\n                self.parent[parentB] = parentA\n                self.rank[parentA] += 1\n\n    def find(self, a):\n        if self.parent[a] == a:\n            return a\n        self.parent[a] = self.find(self.parent[a])\n        return self.parent[a]\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'C', 'Python', 'C++', 'Java', 'Python3']