<p>An <code>n x n</code> grid is composed of <code>1 x 1</code> squares where each <code>1 x 1</code> square consists of a <code>&#39;/&#39;</code>, <code>&#39;\&#39;</code>, or blank space <code>&#39; &#39;</code>. These characters divide the square into contiguous regions.</p>

<p>Given the grid <code>grid</code> represented as a string array, return <em>the number of regions</em>.</p>

<p>Note that backslash characters are escaped, so a <code>&#39;\&#39;</code> is represented as <code>&#39;\\&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/1.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [&quot; /&quot;,&quot;/ &quot;]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/2.png" style="width: 200px; height: 198px;" />
<pre>
<strong>Input:</strong> grid = [&quot; /&quot;,&quot;  &quot;]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/15/4.png" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> grid = [&quot;/\\&quot;,&quot;\\/&quot;]
<strong>Output:</strong> 5
<strong>Explanation: </strong>Recall that because \ characters are escaped, &quot;\\/&quot; refers to \/, and &quot;/\\&quot; refers to /\.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;/&#39;</code>, <code>&#39;\&#39;</code>, or <code>&#39; &#39;</code>.</li>
</ul>

class Solution {
public:
    int findRoot(int x, vector<int> &parent) {
        while(x != parent[x]) {
            x = parent[parent[x]];
        }
        
        return x;
    }
    
    int unite(int x, int y, vector<int> &parent, vector<int> &sz) {
        int rootX = findRoot(x, parent);
        int rootY = findRoot(y, parent);
        
        // No need to unite already united triangles
        if(rootX == rootY) {
            return 0;
        }
        
        // Always keep size of X as greater than size of Y
        if(sz[x] < sz[y]) {
            unite(y, x, parent, sz);
        }
        
        // Now sz[x] >= sz[y] always
        sz[x]+=sz[y];
        parent[rootY] = parent[rootX];
        
        return 1;
    }
    
    int computeIdx(int row, int col, int triangleNumber, int n) {
        return (row*n + col) * 4 + triangleNumber;
    }
    
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        
        unordered_map<string, int> triangleNum;
        triangleNum["top"]=0;
        triangleNum["right"]=1;
        triangleNum["down"]=2;
        triangleNum["left"]=3;
        
        int totalTriangles = n*n*4;
        int regions = totalTriangles;
        
        vector<int> parent(totalTriangles);
        for(int i=0; i<totalTriangles; i++) {
            parent[i] = i;
        }
        
        vector<int> sz(totalTriangles,1);
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                char currChar = grid[i][j];
                
                // unite currCell's top triangle with upperCell's down triangle
                if(i>0) {
                    regions -= unite(computeIdx(i,j,triangleNum["top"],n), computeIdx(i-1,j,triangleNum["down"],n), parent, sz);
                }
                
                // unite currCell's left triangle with leftCell's right triangle
                if(j>0) {
                    regions -= unite(computeIdx(i,j,triangleNum["left"],n), computeIdx(i,j-1,triangleNum["right"],n), parent, sz);
                }
                
                if(currChar != '/') {
                    regions -= unite(computeIdx(i,j,triangleNum["top"],n), computeIdx(i,j,triangleNum["right"],n), parent, sz);
                    regions -= unite(computeIdx(i,j,triangleNum["left"],n), computeIdx(i,j,triangleNum["down"],n), parent, sz);
                }
                
                if(currChar != '\\') {
                    regions -= unite(computeIdx(i,j,triangleNum["top"],n), computeIdx(i,j,triangleNum["left"],n), parent, sz);
                    regions -= unite(computeIdx(i,j,triangleNum["right"],n), computeIdx(i,j,triangleNum["down"],n), parent, sz);
                }
            }
        }
        
        return regions;
    }
};
14988