C++ | Regions Cut By Slashes | 0ms Beats [100.00%]
Intuition\nThe grid with \'/\', \'\\\', and \' \' characters forms regions that are separated by these slashes. By interpreting each cell of the grid as contain
# Intuition\nThe grid with \'/\', \'\\\\\', and \' \' characters forms regions that are separated by these slashes. By interpreting each cell of the grid as containing two parts (top and bottom), we can use union-find to determine how many distinct regions exist. This method involves setting up a union-find data structure to manage and merge these parts based on the given characters.\n\n# Approach\nTo determine the number of distinct regions formed by slashes in a grid, utilize a union-find (disjoint-set) data structure. Treat each cell as having two parts (top and bottom) and initialize union-find for these parts. Iterate through the grid: union the top and bottom parts if the cell contains a space \' \'; union parts of adjacent cells based on \'/\' or \'\\\' characters. Finally, count the unique roots in the union-find structure to find the number of distinct regions.\n\n# Complexity\n- **Time complexity** $$O(n^2)$$, where $$n$$ is the grid dimension, as we process each cell and its neighbors.\n- **Space complexity** $$O(n^2)$$, for the union-find structure managing the top and bottom parts of each cell.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> parent;\n    int findParent(int x) {\n        if (x == parent[x]) return x;\n        parent[x] = findParent(parent[x]);\n        return parent[x];\n    }\n    void unionSets(int x, int y) {\n        int rootX = findParent(x), rootY = findParent(y);\n        if (rootX != rootY) parent[rootX] = rootY;\n    }\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size(), totalNodes = n * n * 2;  \n        parent = vector<int>(totalNodes + 1);\n        int i{1};\n        while (i <= totalNodes) {\n            parent[i] = i;\n            ++i;\n        }\n        int row{0};\n        while (row < n) {\n            int col{0};\n            while (col < n) {\n                int topPart = (row * n + col) * 2 + 1;  \n                int bottomPart = topPart + 1;          \n                if (grid[row][col] == \' \') unionSets(topPart, bottomPart);\n                if (col < n - 1) {  \n                    int leftPart = grid[row][col] == \'/\' ? bottomPart : topPart;\n                    int rightPart = grid[row][col + 1] == \'/\' ? bottomPart + 1 : bottomPart + 2;\n                    unionSets(leftPart, rightPart);\n                }\n                if (row < n - 1) unionSets(bottomPart, topPart + 2 * n);\n                ++col;\n            }\n            ++row;\n        }\n        int regionCount{0};\n        int j{1};\n        while (j <= totalNodes) {\n            if (parent[j] == j) ++regionCount;\n            ++j;\n        }\n        return regionCount;\n    }\n};\n\n```\n## **If you found this solution helpful, please upvote! \uD83D\uDE0A**
['C++']