<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 {
public:
    int bfs(vector<vector<char>>& maze, vector<vector<bool>> visited, int x, int y, int count, int ex, int ey, int m, int n) {
        //
        //cout << x << " " << y << endl;
        //cout << ex << " " << ey << endl;
 
        if ((x == 0 || x == m-1 || y == 0 || y == n-1) && !(x == ex && y == ey)) return count;
        int a = -1, b = -1, c = -1, d = -1;
        if (x-1 >= 0 && maze[x-1][y] == '.' && !visited[x-1][y]) {
            visited[x-1][y] = true;
            a = bfs(maze, visited, x-1, y, count+1, ex, ey, m, n);
        } 
        if (y-1 >= 0 && maze[x][y-1] == '.' && !visited[x][y-1]) {
            visited[x][y-1] = true;
            b = bfs(maze, visited, x, y-1, count+1, ex, ey, m, n);
        }
        if (x+1 < m && maze[x+1][y] == '.' && !visited[x+1][y]) {
            visited[x+1][y] = true;
            c = bfs(maze, visited, x+1, y, count+1, ex, ey, m, n);
        }
        if (y+1 < n && maze[x][y+1] == '.' && !visited[x][y+1]) {
            visited[x][y+1] = true;
            d = bfs(maze, visited, x, y+1, count+1, ex, ey, m, n);
        }
        if (x == 3 && y == 3)
            //cout << a << " " << b << " " << c << " " << d << endl;
        
        if (a == -1 && b == -1 && c == -1 && d == -1) {
            return -1;
        } 

        int e = 0, f = 0;
        if (a != -1 && b != -1) e = min(a, b);
        else {
            e = max(a, b);
        }

        if (c != -1 && d != -1) f = min(c, d);
        else {
            f = max(c, d);
        }

        if (e != -1 && f != -1) return min(e, f);
        else {return max(e, f);}
    }

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size();
        int n = maze[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        visited[entrance[0]][entrance[1]] = true;

        queue<vector<int>> toVisit;
        toVisit.push({entrance[0], entrance[1], 0});
        bool success = false;

        while (!toVisit.empty()) {
            vector<int> cur = toVisit.front();
            toVisit.pop();
            int x = cur[0];
            int y = cur[1];
            //cout << x << " " << y << endl;

            if ((x == 0 || x == m-1 || y == 0 || y == n-1) && !(x == entrance[0] && y == entrance[1])) {
                return cur[2];
            }
            
            if (x-1 >= 0 && maze[x-1][y] == '.' && !visited[x-1][y]) {
                visited[x-1][y] = true;
                toVisit.push({x-1, y, cur[2]+1});
            } 
            if (y-1 >= 0 && maze[x][y-1] == '.' && !visited[x][y-1]) {
                visited[x][y-1] = true;
                toVisit.push({x, y-1, cur[2]+1});
            }
            if (x+1 < m && maze[x+1][y] == '.' && !visited[x+1][y]) {
                visited[x+1][y] = true;
                toVisit.push({x+1, y, cur[2]+1});
            }
            if (y+1 < n && maze[x][y+1] == '.' && !visited[x][y+1]) {
                visited[x][y+1] = true;
                toVisit.push({x, y+1, cur[2]+1});
            }
        }
        return -1;
    }
};
47265