<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:
    vector<vector<int>> front_slash = {{0, 0, 1}, {0, 1, 0}, {1, 0, 0}};
    vector<vector<int>>  back_slash = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    vector<vector<int>>    no_slash = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};

    void make_grid(const vector<string>& string, vector<vector<int>>& output)
    {
        for(int r = 0; r < string.size(); r++)
        {
            for(int c = 0; c < string[r].size(); c++)
            {
                char x = string[r][c];
                if(x == ' ')
                {
                    for(int x = 0; x < 3; x++)
                    {
                        for(int y = 0; y < 3; y++)
                        {
                            output[3 * r + x][3 * c + y] = no_slash[x][y];
                        }
                    }
                }
                else if(x == '/')
                {
                    for(int x = 0; x < 3; x++)
                    {
                        for(int y = 0; y < 3; y++)
                        {
                            output[3 * r + x][3 * c + y] = front_slash[x][y];
                        }
                    }
                }
                else //c == "\\"
                {
                    for(int x = 0; x < 3; x++)
                    {
                        for(int y = 0; y < 3; y++)
                        {
                            output[3 * r + x][3 * c + y] = back_slash[x][y];
                        }
                    }
                }
            }
        }

        // for(int x = 0; x < converted_grid.size(); x++)
        // {
        //     for(int y = 0; y < converted_grid[x].size(); y++)
        //     {
        //         cout << converted_grid[x][y] << " ";
        //     }
        //     cout << endl;
        // }
    }

    void search_for_zero_dfs(vector<vector<int>>& converted_grid, vector<vector<bool>>& visited, int r, int c)
    {
        if(r < 0 || r >= converted_grid.size() || c < 0 || c >= converted_grid[r].size() || visited[r][c] == true || converted_grid[r][c] == 1)
        {
            return;
        }

        visited[r][c] = true;
        search_for_zero_dfs(converted_grid, visited, r + 1, c);
        search_for_zero_dfs(converted_grid, visited, r - 1, c);                         
        search_for_zero_dfs(converted_grid, visited, r, c - 1);
        search_for_zero_dfs(converted_grid, visited, r, c + 1);

    }

    int regionsBySlashes(vector<string>& grid) {
        int sol = 0;
        int n = grid.size();
        vector<vector<int>> converted_grid(3 * n, vector<int>(3 * n, 0));
        make_grid(grid, converted_grid);

        vector<vector<bool>> visited(3 * n, vector<bool>(3 * n, false));
        for(int r = 0; r < converted_grid.size(); r++)
        {
            for(int c = 0; c < converted_grid[r].size(); c++)
            {
                if(converted_grid[r][c] == 0 && !visited[r][c])
                {
                    search_for_zero_dfs(converted_grid, visited, r, c);
                    sol++;
                }
            }
        }

        return sol;
    }
};
16056