<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 UnionFind
{
public:

	UnionFind(int sz)
	{
		parent.resize(sz);
		for (int i = 0; i < sz; i++)
		{
			parent[i] = i;
		}
		size.resize(sz, 1);
	}
	vector<int> parent;
	vector<int> size;

	void uniontriangle(int x, int y)
	{
		int px = findparent(x);
		int py = findparent(y);

		if (px == py) return;

		if (size[px] > size[py])
		{
			parent[py] = px;
			size[px] += 1;
		}
		else
		{
			parent[px] = py;
			size[py] += 1;
		}
	}

	int findparent(int x)
	{
		if (parent[x] != x) {
			parent[x] = findparent(parent[x]);
		}
		return parent[x];
	}
};
class Solution{
public:
	int regions = 0;
	bool isvalid(int i, int j, vector<string>& grid)
	{
		int r = grid.size();
		int c = grid[0].size();
		if (i < 0 || i >= r || j < 0 || j >= c) return false;
		return true;
	}
	int regionsBySlashes(vector<string>& grid) {


		int r = grid.size();
		int c = grid[0].size();

		int num = r * c * 4;
		UnionFind uf(num);
		int regions = 0;
		for (int i = 0; i < r; i++)
		{
			for (int j = 0; j < c; j++)
			{

				int triangle_num = (i * r + j) * 4;

				if (grid[i][j] == '/')
				{
					uf.uniontriangle(triangle_num + 1, triangle_num + 2);
					uf.uniontriangle(triangle_num, triangle_num + 3);
				}

				if (grid[i][j] == '\\')
				{
					uf.uniontriangle(triangle_num + 3, triangle_num + 2);
					uf.uniontriangle(triangle_num, triangle_num + 1);
				}
				if (grid[i][j] == ' ')
				{
					uf.uniontriangle(triangle_num + 3, triangle_num + 2);
					uf.uniontriangle(triangle_num, triangle_num + 1);
					uf.uniontriangle(triangle_num + 3, triangle_num + 1);
				}
				// top
				if (i - 1 >= 0)
				{
					uf.uniontriangle(triangle_num - (4 * c) + 2, triangle_num);
				}
				// down
				if (i + 1 < r)
				{
					uf.uniontriangle(triangle_num + (4 * c), triangle_num + 2);
				}

				// left

				if (j - 1 >= 0)
				{
					uf.uniontriangle(triangle_num - (4) + 1, triangle_num + 3);
				}
				//right
				if (j + 1 <c)
				{
					uf.uniontriangle(triangle_num + (4) + 3, triangle_num + 1);
				}
			}
		}

		for (int i = 0; i < uf.parent.size(); i++)
		{
			if (uf.findparent(i) == i)
			{
				regions++;
			}
		}


		return regions;
	}
};
12548