<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>

#union find:
#for each cell divided to 4 cells, E,W,S,N. Then traverse all seperate cells in the grid., and union find to connect all cell based on the different case. We need to deal with inner case and inter case!
class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        #initialization:
        size = len(grid)
        #record the root for each cell.
        root = {}
        #rank for the path compression and manitain the height!
        rank = {}
        for i in range(size):
            for j in range(size):
                #update the status for each component!
                root[(i,j,'N')] = (i,j,'N')
                root[(i,j,'S')] = (i,j,'S')
                root[(i,j,'W')] = (i,j,'W')
                root[(i,j,'E')] = (i,j,'E')
                #update the rank for each componnet:
                rank[(i,j,'N')] = 1
                rank[(i,j,'S')] = 1
                rank[(i,j,'W')] = 1
                rank[(i,j,'E')] = 1
        #untion find algorithm:
        def find(node):
            #base case:
            if root[node] == node:
                return node
            #path compression:
            root[node] = find(root[node])
            #return current node:
            return root[node]
        #union algorithm:
        def union(n1,n2):
            #find the parent node!
            p1,p2 = find(n1),find(n2)
            #reunion:
            if rank[p1] > rank[p2]:
                root[p2] = p1 
            elif rank[p1] < rank[p2]:
                root[p1] = p2
            else:
                root[p2] = p1
                #update rank as well:
                rank[p1] += 1
        #uinion and find!
        for i in range(size):
            for j in range(size):
                #inner cell:
                if grid[i][j] == " ":
                    union((i,j,'N'),(i,j,'E'))
                    union((i,j,'S'),(i,j,'W'))
                    union((i,j,'E'),(i,j,'W'))
                elif grid[i][j] == '/':
                    union((i,j,'N'),(i,j,'W'))
                    union((i,j,'S'),(i,j,'E'))
                elif grid[i][j] == '\\':
                    union((i,j,'N'),(i,j,'E'))
                    union((i,j,'S'),(i,j,'W'))
                #inter cell:
                if i > 0:
                    union((i,j,'N'),(i-1,j,'S'))
                if j > 0:
                    union((i,j-1,'E'),(i,j,'W'))
        #find how many parents:
        res = set()
        for key in root:
            res.add(find(key))
        return len(res)

         



23649