<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 DisJointSet{
    private:    
    vector<int> parent, rank;
    public:
    DisJointSet(int n){
        parent.resize(n), rank.resize(n, 1);
        for(int i = 0; i<n; i++) parent[i] = i;
    }

    int getUltPar(int n){
        if(parent[n] == n) return n;
        return parent[n] = getUltPar(parent[n]);
    }

    void unionByRank(int u, int v){
        int ultp_U = getUltPar(u), ultp_V = getUltPar(v);
        if(ultp_U == ultp_V) return;
        int rank_U = rank[ultp_U], rank_V = rank[ultp_V];
        if(rank_U == rank_V){
            parent[ultp_U] = ultp_V;
            rank[ultp_V] += 1;
        }else if(rank_U > rank_V){
            parent[ultp_V] = ultp_U;
        }else{
            parent[ultp_U] = ultp_V;
        }
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size(), ans = 0;
        vector<vector<int> > v;
        for(int i = 0; i<n; i++){
            vector<int> first, second, third;
            for(int j = 0; j<n; j++){
                if(grid[i][j] == ' '){
                    first.push_back(0), first.push_back(0), first.push_back(0);
                    second.push_back(0), second.push_back(0), second.push_back(0);
                    third.push_back(0), third.push_back(0), third.push_back(0);
                }else if(grid[i][j] == '\\'){
                    first.push_back(1), first.push_back(0), first.push_back(0);
                    second.push_back(0), second.push_back(1), second.push_back(0);
                    third.push_back(0), third.push_back(0), third.push_back(1);
                }else{
                    first.push_back(0), first.push_back(0), first.push_back(1);
                    second.push_back(0), second.push_back(1), second.push_back(0);
                    third.push_back(1), third.push_back(0), third.push_back(0);
                }
            }

            v.push_back(first), v.push_back(second), v.push_back(third);
        }

        DisJointSet uf(v.size()*v.size());
        int x[4] = {-1, 1, 0, 0}, y[4] = {0, 0, -1, 1};
        for(int i = 0; i<v.size(); i++){
            for(int j = 0; j<v[i].size(); j++){
                if(v[i][j] == 0){
                    for(int l = 0; l<4; l++){
                        int r = i + x[l], c = j + y[l];
                        if(r >= 0 && r < v.size() && c >= 0 && c < v[i].size() && v[r][c] == 0)
                            uf.unionByRank((i*v.size())+j, (r*v.size())+c);
                    }
                }
            }
        }

        for(int i = 0; i<v.size(); i++){
            for(int j = 0; j<v[i].size(); j++){
                if(v[i][j] == 0 && (i*v.size())+j == uf.getUltPar((i*v.size())+j)) ans += 1;
            }
        }

        return ans;
    }
};
21698