<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:
    def __init__(self):
        # self.left_match = ['ru', 'rd', 'o']
        self.n = 0

    def left_match(self, r,c):
        return [(r,c-1,'ru'), (r,c-1,'rd'), (r,c-1,'o')]
    
    def up_match(self, r,c):
        return [(r-1,c,'ld'), (r-1,c,'rd'), (r-1,c,'o')]
    
    def down_match(self, r,c):
        return [(r+1,c,'lu'), (r+1,c,'ru'), (r+1,c,'o')]
    
    def right_match(self, r,c):
        return [(r,c+1,'lu'), (r,c+1,'ld'), (r,c+1,'o')]
    
    def neighbors(self, r, c, t, nodes):
        n = self.n
        candidates = []
        if t == 'lu':
            if c - 1 >= 0: # left
                candidates.extend(self.left_match(r,c))
            if r - 1 >= 0: # up
                candidates.extend(self.up_match(r,c))
        elif t == 'ld':
            if c - 1 >= 0: # left
                candidates.extend(self.left_match(r,c))
            if r+1 < n: # down
                candidates.extend(self.down_match(r,c))
        elif t == 'ru':
            if c + 1 < n: # right
                candidates.extend(self.right_match(r,c))
            if r-1 >= 0: # up
                candidates.extend(self.up_match(r,c))
        elif t == 'rd':
            if c + 1 < n: # right
                candidates.extend(self.right_match(r,c))
            if r+1 < n: # down
                candidates.extend(self.down_match(r,c))
        elif t == 'o':
            if c - 1 >= 0: # left
                candidates.extend(self.left_match(r,c))
            if r - 1 >= 0: # up
                candidates.extend(self.up_match(r,c))
            if c + 1 < n: # right
                candidates.extend(self.right_match(r,c))
            if r+1 < n: # down
                candidates.extend(self.down_match(r,c))
        else:
            raise
        output = []
        for ca in candidates:
            if ca not in nodes:
                continue
            output.append(ca)
        return output

    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        self.n = n
        # create graph data
        # count connected components
        
        # cell with / or \ accounts for two nodes left and right
        # / : left: [left, up]   right: [right, down]
        # lu, rd
        # \ : left: [left, down] right: [right, up]
        # ld, ru
        #' ': a single node able to connect in all directions

        # nodes can be enumerated by (i,j, dir) where dir = left | right | omni
        #                                                   -1, 1, 0 

        nodes = set()
        for i, row in enumerate(grid):
            for j,ch in enumerate(row):
                if ch == ' ':
                    nodes.add((i,j,'o'))
                elif ch == '/':
                    nodes.add((i,j,'lu'))
                    nodes.add((i,j,'rd'))
                else:
                    nodes.add((i,j,'ld'))
                    nodes.add((i,j,'ru'))
            # j = 0
            # index = 0
            # while j < n:
            #     if row[index] == ' ':
            #         nodes.add((i,j,'o'))
            #         index += 1
            #     elif row[index] == '/':
            #         nodes.add((i,j,'lu'))
            #         nodes.add((i,j,'rd'))
            #         index += 1
            #     else:
            #         nodes.add((i,j,'ld'))
            #         nodes.add((i,j,'ru'))
            #         index += 2
            #     j += 1
        
        seen = set()
        components = 0
        # dfs at each elem
        for node in nodes:
            if node in seen:
                continue
            #dfs here
            stack = [node]
            print("node:", node)
            while stack:
                r,c, t = stack.pop()
                seen.add((r,c,t))
                ngbrs = self.neighbors(r,c,t, nodes)
                print("ngbors:", ngbrs)
                for x in ngbrs:
                    if x not in seen:
                        print("x:", x)
                        stack.append(x)
                
            components += 1
        return components

                # mark it as seen
                # check out if its ngbors exist in nodes and add them to the stack if not already seen
                # ngbors are defined based on type t
                # 'o' -> (r,c-1, ru or rd or o) left
                #     -> (r, c+ 1, lu | ld | o ) right
                #.    -> (r-1, c, ld | rd | o) up
                #     -> (r+1, c, lu | ru | o)
17450