[Java/C++/Python] Split 4 parts and Union Find
Intuition\nSplit a cell in to 4 parts like this.\nWe give it a number top is 0, right is 1, bottom is 2 left is 3.\n\n\n(photo by @Sabbi_coder)\n\nTwo adjacent 
# **Intuition**\nSplit a cell in to 4 parts like this.\nWe give it a number top is 0, right is 1, bottom is 2 left is 3.\n\n![image](https://assets.leetcode.com/users/images/c1f05c28-9c76-4211-b25a-4fe8df539938_1600322994.7242403.png)\n(photo by @Sabbi_coder)\n\nTwo adjacent parts in different cells are contiguous regions.\nIn case `\'/\'`, top and left are contiguous, botton and right are contiguous.\nIn case `\'\\\\\'`, top and right are contiguous, bottom and left are contiguous.\nIn case `\' \'`, all 4 parts are contiguous.\n\nCongratulation.\nNow you have another problem of counting the number of islands.\n<br>\n\n# **Explanation**\nDFS will be good enough to solve it.\nAs I did in [947.Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197668)\nI solved it with union find.\n<br>\n\n# **Complexity**\nTime `O(N^2)`\nSpace `O(N^2)`\n<br>\n\n**Java**\ncommented by @user3929Z\n```cpp\n    int count, n;\n    int[] f;\n    public int regionsBySlashes(String[] grid) {\n        n = grid.length;\n        f = new int[n * n * 4];  //build an array to store all parents of all triangles\n        count = n * n * 4;        //total number of polygons\n        for (int i = 0; i < n * n * 4; ++i)    //initialize the parent array\n            f[i] = I;\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i > 0) union(g(i - 1, j, 2), g(i, j, 0));   // merge triangles 2 and 0 from two squares vertically\n                if (j > 0) union(g(i , j - 1, 1), g(i , j, 3)); // merge trianges 1 and 3 from two squares horizontally. These triangles are supposed to be contiguous originally\n                if (grid[i].charAt(j) != \'/\') {                      // if it is "\\\\" or empty, apply common operations\n                    union(g(i , j, 0), g(i , j,  1));\n                    union(g(i , j, 2), g(i , j,  3));\n                }\n                if (grid[i].charAt(j) != \'\\\\\') {              // if it is "/" or empty, apply common operations.\n                    union(g(i , j, 0), g(i , j,  3));         // These two if statements solve the repetition issue caused by traditional three if statements\n                    union(g(i , j, 2), g(i , j,  1));\n                }\n            }\n        }\n        return count;               //return number of polygons in the graph\n    }\n\n    public int find(int x) {\n        if (x != f[x]) {\n            f[x] = find(f[x]);  //path compression\n        }\n        return f[x];\n    }\n    public void union(int x, int y) {     //merge two polygons to a bigger polygon will decrease number of polygons by 1\n        x = find(x); y = find(y);\n        if (x != y) {\n            f[x] = y;\n            count--;\n        }\n    }\n    public int g(int i, int j, int k) {    //find the corresponding position for current triangle. Thinks this 1D array as a 2D array and each element is an array of size 4.\n        return (i * n + j) * 4 + k;\n    }\n```\n\n**C++**\n```cpp\n   int count, n;\n   vector<int> f;\n   int regionsBySlashes(vector<string>& grid) {\n        n = grid.size();\n        count = n * n * 4;\n        for (int i = 0; i < n * n * 4; ++i)\n            f.push_back(i);\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i > 0) uni(g(i - 1, j, 2), g(i, j, 0));\n                if (j > 0) uni(g(i , j - 1, 1), g(i , j, 3));\n                if (grid[i][j] != \'/\') {\n                    uni(g(i , j, 0), g(i , j,  1));\n                    uni(g(i , j, 2), g(i , j,  3));\n                }\n                if (grid[i][j] != \'\\\\\') {\n                    uni(g(i , j, 0), g(i , j,  3));\n                    uni(g(i , j, 2), g(i , j,  1));\n                }\n            }\n        }\n        return count;\n    }\n\n    int find(int x) {\n        if (x != f[x]) {\n            f[x] = find(f[x]);\n        }\n        return f[x];\n    }\n    void uni(int x, int y) {\n        x = find(x); y = find(y);\n        if (x != y) {\n            f[x] = y;\n            count--;\n        }\n    }\n    int g(int i, int j, int k) {\n        return (i * n + j) * 4 + k;\n    }\n```\n**Python:**\n```py\n    def regionsBySlashes(self, grid):\n        f = {}\n        def find(x):\n            f.setdefault(x, x)\n            if x != f[x]:\n                f[x] = find(f[x])\n            return f[x]\n        def union(x, y):\n            f[find(x)] = find(y)\n\n        for i in xrange(len(grid)):\n            for j in xrange(len(grid)):\n                if i:\n                    union((i - 1, j, 2), (i, j, 0))\n                if j:\n                    union((i, j - 1, 1), (i, j, 3))\n                if grid[i][j] != "/":\n                    union((i, j, 0), (i, j, 1))\n                    union((i, j, 2), (i, j, 3))\n                if grid[i][j] != "\\\\":\n                    union((i, j, 3), (i, j, 0))\n                    union((i, j, 1), (i, j, 2))\n        return len(set(map(find, f)))\n```\n
[]