An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a '\' is represented as '\\'.

&nbsp;
Example 1:

Input: grid = [" /","/ "]
Output: 2


Example 2:

Input: grid = [" /","  "]
Output: 1


Example 3:

Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.


&nbsp;
Constraints:


	n == grid.length == grid[i].length
	1 &lt;= n &lt;= 30
	grid[i][j] is either '/', '\', or ' '.


class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n=len(grid)
        dots=n+1
        par=[0]*(dots*dots)
        rank=[0]*(dots*dots)
        self.count=1

        def find(x):
            if par[x]==x:
                return x
            temp=find(par[x])
            par[x]=temp
            return temp
        def union(x,y):
            lx=find(x)
            ly=find(y)
            if lx!=ly:
                if rank[lx]>rank[ly]:
                    par[ly]=lx
                elif rank[lx]<rank[ly]:
                    par[lx]=ly
                else:
                    par[lx]=ly
                    rank[ly]+=1
            else:
                self.count+=1
    #-------------------------------------------#
        for i in range(len(par)):
            par[i]=i
            rank[i]=1
        for i in range(dots):
            for j in range(dots):
                if i==0 or j==0 or i==dots-1 or j==dots-1:
                    cellno=i*dots+j
                    if cellno!=0:
                        union(0,cellno)
        for i in range(len(grid)):
            ch=grid[i]
            for j in range(len(ch)):
                if ch[j]=='/':
                    cellno1=i*dots+j+1
                    cellno2=(i+1)*dots+j

                    union(cellno1,cellno2)
                elif ch[j]=='\\':
                    cellno1=i*dots+j
                    cellno2=(i+1)*dots+j+1
                    union(cellno1,cellno2)
        return self.count
class Solution {
    int[] parent;
    int[] rank;
    
    public int regionsBySlashes(String[] grid) {
        parent = new int[4*grid.length*grid.length];
        rank = new int[4*grid.length*grid.length];
        
        for(int i=0;i<parent.length;i++){
            parent[i] = i;
            rank[i] = 0;
        }
        
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length();j++){
                char ch = grid[i].charAt(j);
                
                int bno = i * grid.length + j;
                
                if(ch != '/'){
                    unionHelper(4*bno + 0 , 4*bno + 1);
                    unionHelper(4*bno + 2, 4*bno + 3);
                }
                
                if(ch != '\\'){
                    unionHelper(4*bno + 0 , 4*bno + 3);
                    unionHelper(4*bno + 1, 4*bno + 2);
                }
                
                if(i > 0){
                    int obno = (i-1) * grid.length + j;
                    unionHelper(4*bno + 0 , 4*obno + 2);
                }
                
                if(j > 0){
                    int obno = i * grid.length + (j-1);
                    unionHelper(4*bno + 3 , 4*obno + 1);
                }
                
            }
        }
        
        int count = 0;
        
        for(int i=0;i<parent.length;i++){
            if(parent[i] == i){
                count++;
            }
        }
        
        return count;       
        
    }
    
    
    public int find(int x){
        if(parent[x] == x){
            return parent[x];
        }else{
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
    public void union(int xl,int yl){
        if(rank[xl] < rank[yl]){
            parent[xl] = yl;
        }else if(rank[yl] < rank[xl]){
            parent[yl] = xl;
        }else{
            parent[xl] = yl;
            rank[yl]++;
        }
    }
    public void unionHelper(int x,int y){
        int xl = find(x);
        int yl = find(y);
        
        if(xl != yl){
            union(xl,yl);
        }
    }
}
/*
Convert grid to 3*n X 3*n grid where eacah of the cell is upscalled to 3x3 grid
and then map the diagonal to 0 or 1 depending on '/' or '\' type in the grid.

Example:
["/\\","\\/"] this can be converted to following scaled grid:

1 1 0 0 1 1 
1 0 1 1 0 1 
0 1 1 1 1 0 
0 1 1 1 1 0 
1 0 1 1 0 1 
1 1 0 0 1 1 

Once this conversion is done, then its simple island count problem, run dfs from each cell 
to visit all cells and count number of times dfs is started and return it as answer.
*/

class Solution {
public:
    int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    void dfs(vector<vector<int>>& g, vector<vector<int>>& vis, int i, int j){
        for(int d = 0; d<4; ++d){
            int x = i + dir[d][0];
            int y = j + dir[d][1];
            if( x >= 0 && y >= 0 && x < g.size() && y < g.size() && 
                vis[x][y] == -1 && g[x][y] == 1){
                vis[x][y] = 1;
                dfs(g, vis, x, y);
            }
        }
    }
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        vector<vector<int>> g(3*n, vector<int> (3*n, 1)); 
        for(int i = 0; i < n; ++i){
            for(int j = 0; j< n; ++j){
                if(grid[i][j] == '\\'){
                   for(int k = 0; k < 3; ++k) g[3*i+k][3*j+k] = 0;
                }
                else if(grid[i][j] == '/'){
                   for(int k = 0; k < 3; ++k) g[3*i+k][3*j+ 2-k] = 0;
                }
            }
        }
        int count = 0;
        vector<vector<int>> vis(3*n, vector<int> (3*n, -1));
        
        for(int i = 0; i < 3*n; ++i){
            for(int j = 0; j < 3*n; ++j){
                if(vis[i][j] == -1 && g[i][j] == 1){ //cout<<i<<" "<<j<<endl;
                    count++;
                    vis[i][j] = 1;
                    dfs(g, vis, i, j);
                }
            }
        }
         
        return count;
    }
};
// this is a very common disjoint set implement
function DS(n) {
    var root = [...new Array(n).keys()];
    var rank = new Array(n).fill(0);
    this.find = function(v) {
        if (root[v] !== v) root[v] = this.find(root[v]);
        return root[v];
    }
    this.union = function(i, j) {
        var [ri, rj] = [this.find(i), this.find(j)];
        if (ri === rj) return;
        if (rank[ri] > rank[rj]) root[rj] = ri;
        else if (rank[ri] < rank[rj]) root[ri] = rj;
        else root[ri] = rj, rank[rj]++;
    }
	// get how many unique unions
    this.getUnoinCount = function() {
        for (var i = 0; i < n; i++) this.find(i);
        return new Set(root).size;
    }
}

function getKeys(i, j, n) {
    var val = i * n + j;
    val *= 2;
	// left and right part key of grid[i][j]
    return [val, val + 1];
}

/**
 * @param {string[]} grid
 * @return {number}
 */
var regionsBySlashes = function(grid) {
    var n = grid.length;
    if (n === 1) return grid[0][0] === ' ' ? 1 : 2;
    var ds = new DS(n * n * 2);
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            var [left, right] = getKeys(i, j, n);
			// When this cell is ' ', union left and right.
            if (grid[i][j] === ' ') ds.union(left, right);
			// if have upper neighbor
            if (i !== 0) {
                var [upLeft, upRight] = getKeys(i - 1, j, n);
				// For upper neighbor, if it's '/', we should choose right part to union, if '\', choose left.
                var upKey = grid[i - 1][j] === '\\' ? upLeft : upRight;
				// For current cell, if it's '/', we should choose left part to union, if '\', choose right.
                var curKey = grid[i][j] === '/' ? left : right;
                ds.union(upKey, curKey);
            }
			// if have left neighbor
            if (j !== 0) {
                var [leftLeft, leftRight] = getKeys(i, j - 1, n);
				// just choose the right part of the left neighbor
                var leftKey = leftRight;
				// just choose the left part of the current cell
                var curKey = left;
                ds.union(leftKey, curKey);
            }
        }
    }
    return ds.getUnoinCount();
};
Regions Cut By Slashes