Java Solution with pictorial representation and FULL explanantion
As mentioned everywhere, the idea is to represent each cell with a set of 4 triangles (call it north, west, south and east in the anti-clockwise order). For the
As mentioned everywhere, the idea is to represent each cell with a set of 4 triangles (call it north, west, south and east in the anti-clockwise order). For the given example shown in the image, the set of triangles for each cell are numbered accordingly. \n\nwhile traversing each cell, we will get determine the index of the root triangle of that cell, and connect with all other triangles depending on the character present in that cell.\n\nThe corresponding graphical representation of the connected triangles is also shown in the image. Now, the question remains, find the number of components in a graph. You can use either union-find or DFS approach to determine the number of connected components. I have used Union-Find. \n\n![image](https://assets.leetcode.com/users/parin2/image_1585033819.png)\n\n**The Java Solution:**\n\n```\nprivate class UF {\n\tint[] parents;\n\tUF(int n) {\n\t\tparents = new int[n];\n\t\tArrays.fill(parents, -1);\n\t}\n\n\tvoid union(int u, int v) {\n\t\t// System.out.println("Uniting " + u + " " + v);\n\t\tint uf = find(u),\n\t\t\tvf = find(v);\n\n\t\tif (uf == vf) {\n\t\t\t// System.out.println("Already united: " + u + " " + v);\n\t\t\treturn; // already united\n\t\t}\n\n\t\tif (parents[uf] <= parents[vf]) {\n\t\t\tparents[uf] += parents[vf];\n\t\t\tparents[vf] = uf;\n\n\t\t} else {\n\t\t\tparents[vf] += parents[uf];\n\t\t\tparents[uf] = vf;\n\n\t\t}\n\t}\n\n\tint find(int u) {\n\t\tint cur = u;\n\t\twhile (parents[cur] >= 0) {\n\t\t\tcur = parents[cur];\n\t\t}\n\n\t\tif (parents[u] >= 0) {\n\t\t\tparents[u] = cur;\n\t\t}\n\n\t\treturn cur;\n\t}\n\n\tint getNoOfComponents() {\n\t\tint res = 0;\n\t\tfor (int p : parents) {\n\t\t\tif (p < 0) {\n\t\t\t\t++res;\n\t\t\t}\n\t\t}\n\n\t\treturn res;\n\t}\n\n\tvoid print() {\n\t\t// System.out.println(Arrays.toString(parents));\n\t}\n}\n\npublic int regionsBySlashes(String[] grid) {\n\tint rows = grid.length,\n\t\tcols = grid[0].length(); // since, it\'s n x n matrix\n\n\tUF uf = new UF(rows*cols*4);\n\n\tfor (int i = 0; i < rows; i++) {\n\t\tfor (int j = 0; j < cols; j++) {\n\t\t\tint root = (4*i*rows) // number of triangles covered in prior rows \n\t\t\t\t\t\t+ (4*j); // number of triangles covered in this row\n\n\t\t\tchar ch = grid[i].charAt(j);\n\t\t\tif (ch == \' \') {\n\t\t\t\t// connect all 4 triangles in a cell\n\t\t\t\tuf.union(root, root + 1);\n\t\t\t\tuf.union(root+1, root+2);\n\t\t\t\tuf.union(root+2, root+3);\n\t\t\t\tuf.union(root+3, root);\n\n\t\t\t} else if (ch == \'/\') {\n\t\t\t\tuf.union(root, root+1);\n\t\t\t\tuf.union(root+2, root+3);\n\n\t\t\t} else if (ch == \'\\\\\') {\n\t\t\t\tuf.union(root, root+3);\n\t\t\t\tuf.union(root+1, root+2);\n\n\t\t\t}\n\n\t\t\t// connect north triangle of this cell to the south triangle of the north cell\n\t\t\tif (i - 1 >= 0) {\n\t\t\t\tint northRoot = (4*(i-1)*rows) + (4*j);\n\t\t\t\tuf.union(root, northRoot+2);\n\t\t\t}\n\n\t\t\t// connect west triangle of this cell to the east triangle of the west cell\n\t\t\tif (j - 1 >= 0) {\n\t\t\t\tint westRoot = root - 4;\n\t\t\t\tuf.union(root+1, westRoot + 3);\n\t\t\t}\n\n\t\t\t// connect south triangle of this cell to the north triangle of the south cell\n\t\t\tif (i + 1 < rows) {\n\t\t\t\tint southRoot = 4*(i+1)*rows + (4*j);\n\t\t\t\tuf.union(root+2, southRoot);\n\t\t\t}\n\n\t\t\t// connect east triangle of this cell to the west triangle of the east cell\n\t\t\tif (j + 1 < cols) {\n\t\t\t\tint eastRoot = (4*i*rows) + (4*(j+1));\n\t\t\t\tuf.union(root+3, eastRoot+1);\n\t\t\t}\n\t\t}\n\t}\n\tuf.print();\n\n\treturn uf.getNoOfComponents();\n}\n```
[]