<p>You are given an <code>m x n</code> matrix <code>maze</code> (<strong>0-indexed</strong>) with empty cells (represented as <code>&#39;.&#39;</code>) and walls (represented as <code>&#39;+&#39;</code>). You are also given the <code>entrance</code> of the maze, where <code>entrance = [entrance<sub>row</sub>, entrance<sub>col</sub>]</code> denotes the row and column of the cell you are initially standing at.</p>

<p>In one step, you can move one cell <strong>up</strong>, <strong>down</strong>, <strong>left</strong>, or <strong>right</strong>. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the <strong>nearest exit</strong> from the <code>entrance</code>. An <strong>exit</strong> is defined as an <strong>empty cell</strong> that is at the <strong>border</strong> of the <code>maze</code>. The <code>entrance</code> <strong>does not count</strong> as an exit.</p>

<p>Return <em>the <strong>number of steps</strong> in the shortest path from the </em><code>entrance</code><em> to the nearest exit, or </em><code>-1</code><em> if no such path exists</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg" style="width: 333px; height: 253px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;+&quot;,&quot;+&quot;,&quot;.&quot;,&quot;+&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;,&quot;+&quot;],[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;,&quot;.&quot;]], entrance = [1,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearesr2-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;],[&quot;.&quot;,&quot;.&quot;,&quot;.&quot;],[&quot;+&quot;,&quot;+&quot;,&quot;+&quot;]], entrance = [1,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/nearest3-grid.jpg" style="width: 173px; height: 93px;" />
<pre>
<strong>Input:</strong> maze = [[&quot;.&quot;,&quot;+&quot;]], entrance = [0,0]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There are no exits in this maze.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>maze.length == m</code></li>
	<li><code>maze[i].length == n</code></li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
	<li><code>maze[i][j]</code> is either <code>&#39;.&#39;</code> or <code>&#39;+&#39;</code>.</li>
	<li><code>entrance.length == 2</code></li>
	<li><code>0 &lt;= entrance<sub>row</sub> &lt; m</code></li>
	<li><code>0 &lt;= entrance<sub>col</sub> &lt; n</code></li>
	<li><code>entrance</code> will always be an empty cell.</li>
</ul>

class Solution: # from entrance
    def getExits(self, maze, entrance):
        exitNodes = set() 
        entrance_set = (entrance[0], entrance[1])
        # row traverse
        for row in range(len(maze)):
            left_coor = (row, 0)
            if maze[left_coor[0]][left_coor[1]] == "." and left_coor != entrance_set:
                exitNodes.add(left_coor)
            right_coor = (row, len(maze[0])-1)
            if maze[right_coor[0]][right_coor[1]] == "."  and right_coor != entrance_set:
                exitNodes.add(right_coor)   
        # col traverse
        for col in range(1, (len(maze[0])-1)):
            upper_coor = (0, col)
            if maze[upper_coor[0]][upper_coor[1]] == "." and upper_coor != entrance_set:
                exitNodes.add(upper_coor)
            lower_coor = (len(maze)-1, col)
            if maze[lower_coor[0]][lower_coor[1]] == "." and lower_coor != entrance_set:
                exitNodes.add(lower_coor)     
        return exitNodes


    def nearestExit(self, maze, entrance):
        exitNodes = self.getExits(maze, entrance)
        n_rows, n_cols = len(maze), len(maze[0])
        all_nodes = deque()  # store all nodes in all levels
        all_nodes.append([entrance[0],entrance[1],0]) # each is (coor_ver,coord_col,n_step)
        is_visited = set()
        is_visited.add((entrance[0],entrance[1]))

        # get the child (neighbors)
        def getChild(coor,step):
            child = []
            directions = [[0,-1],[-1,0],[0,1],[1,0]]
            for (row_offside, col_offside) in directions:
                new_coor = [coor[0]+row_offside, coor[1]+col_offside, step+1] 
                if new_coor[0] >= 0 and new_coor[0] < n_rows and new_coor[1] >= 0 \
                   and new_coor[1] < n_cols and new_coor != entrance \
                   and maze[new_coor[0]][new_coor[1]] == "." \
                   and not ((new_coor[0],new_coor[1]) in is_visited):
                    child.append(new_coor) 
                    # mark current node as visited
                    is_visited.add((new_coor[0],new_coor[1]))
            return child
        
        # main loop
        while all_nodes:
            row, col, step = all_nodes.popleft()
            # get neighbors
            new_child = getChild([row, col], step)
            if len(new_child) > 0:
                all_nodes.extend(new_child)
            # check if current node is in exit door
            if (row, col) in exitNodes:
                return step

        return -1

# class Solution: # from exit
#     def getExits(self, maze, entrance):
#         exitNodes = []
#         # row traverse
#         for row in range(len(maze)):
#             left_coor = [row, 0, 0]
#             if maze[left_coor[0]][left_coor[1]] == "." and left_coor[:2] != entrance:
#                 exitNodes.append(left_coor)
#             right_coor = [row, len(maze[0])-1, 0]
#             if maze[right_coor[0]][right_coor[1]] == "."  and right_coor[:2] != entrance:
#                 exitNodes.append(right_coor)   
#         # col traverse
#         for col in range(1, (len(maze[0])-1)):
#             upper_coor = [0, col, 0]
#             if maze[upper_coor[0]][upper_coor[1]] == "." and upper_coor[:2] != entrance:
#                 exitNodes.append(upper_coor)
#             lower_coor = [len(maze)-1, col, 0]
#             if maze[lower_coor[0]][lower_coor[1]] == "." and lower_coor[:2] != entrance:
#                 exitNodes.append(lower_coor)     
#         return exitNodes


#     def nearestExit(self, maze, entrance):
#         exitNodes = self.getExits(maze, entrance)
#         n_rows, n_cols = len(maze), len(maze[0])
#         all_nodes = deque()  # store all nodes in all levels
#         all_nodes.extend(exitNodes) # each is [coor_ver, coord_col, n_step]
#         is_visited = set()

#         # get the child (neighbors)
#         def getChild(coor,step):
#             child = []
#             directions = [[0,-1],[-1,0],[0,1],[1,0]]
#             for (row_offside, col_offside) in directions:
#                 new_coor = [coor[0]+row_offside, coor[1]+col_offside, step+1] 
#                 if new_coor[0] >= 0 and new_coor[0] < n_rows and new_coor[1] >= 0 \
#                    and new_coor[1] < n_cols and new_coor != entrance \
#                    and maze[new_coor[0]][new_coor[1]] == "." \
#                    and not ((new_coor[0],new_coor[1]) in is_visited):
#                     child.append(new_coor) 
#                     # mark current node as visited
#                     is_visited.add((new_coor[0],new_coor[1]))
#             return child
        
#         # main loop
#         while all_nodes:
#             row, col, step = all_nodes.popleft()
#             # get neighbors
#             new_child = getChild([row, col], step)
#             if len(new_child) > 0:
#                 all_nodes.extend(new_child)
#             # check if current node is in exit door
#             if [row, col] == entrance:
#                 return step
#         return -1
        
724