<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:
    def is_empty(self, maze: List[List[str]], location: List[int]) -> bool:
        return maze[location[0]][location[1]] == "."

    def is_exit(self, maze: List[List[str]], location: List[int]) -> bool:
        num_rows = len(maze)
        num_cols = len(maze[0])

        return (self.is_empty(maze, location) and
                (location[0] == 0 or location[0] == num_rows - 1 or
                location[1] == 0 or location[1] == num_cols - 1))

    def is_valid(self, maze: List[List[str]], location: List[int]) -> bool:
        num_rows = len(maze)
        num_cols = len(maze[0])

        return (location[0] >= 0 and location[0] < num_rows and
                location[1] >= 0 and location[1] < num_cols)

    def get_neighbors(self, maze: List[List[str]], location: List[int], visited: List[List[bool]]) -> List[List[int]]:
        candidates = [
            [location[0] - 1, location[1]],     # up
            [location[0] + 1, location[1]],     # down
            [location[0], location[1] - 1],     # left
            [location[0], location[1] + 1]      # right
        ]

        # Remove candidates which are not in the board or aren't empty
        index = 0
        while index < len(candidates):
            candidate = candidates[index]
            if self.is_valid(maze, candidate) and self.is_empty(maze, candidate):
                index += 1
            else:
                del candidates[index]
        
        return candidates
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        num_rows = len(maze)
        num_cols = len(maze[0])

        # Keep track of which locations we have visited
        visited = [[False for _ in range(num_cols)] for _ in range(num_rows)]
        visited[entrance[0]][entrance[1]] = True

        # How many steps it takes to get from the entrance to each location in the queue
        steps = 1
        queue: List[List[int]] = self.get_neighbors(maze, entrance, visited)

        while len(queue) > 0:
            # Empty the queue of the locations which correspond to the step count
            layer_size = len(queue)
            for _ in range(layer_size):
                location = queue.pop(0)

                # Skip over locations already visited
                if visited[location[0]][location[1]]:
                    continue
                visited[location[0]][location[1]] = True

                if self.is_exit(maze, location):
                    # If this is an exit, we have our solution
                    return steps
                else:
                    # Queue all non-visited empty neighbors to the queue
                    for location in self.get_neighbors(maze, location, visited):
                        queue.append(location)
            steps += 1
        
        # No such path was found
        return -1
        
17400