You are given an `m x n`

matrix `maze`

(**0-indexed**) with empty cells (represented as `'.'`

) and walls (represented as `'+'`

). You are also given the `entrance`

of the maze, where `entrance = [entrance`

denotes the row and column of the cell you are initially standing at._{row}, entrance_{col}]

In one step, you can move one cell **up**, **down**, **left**, or **right**. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the **nearest exit** from the `entrance`

. An **exit** is defined as an **empty cell** that is at the **border** of the `maze`

. The `entrance`

**does not count** as an exit.

Return *the number of steps in the shortest path from the *

`entrance`

`-1`

**Example 1:**

Input:maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]Output:1Explanation: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.

**Example 2:**

Input:maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]Output:2Explanation: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.

**Example 3:**

Input:maze = [[".","+"]], entrance = [0,0]Output:-1Explanation:There are no exits in this maze.

**Constraints:**

`maze.length == m`

`maze[i].length == n`

`1 <= m, n <= 100`

`maze[i][j]`

is either`'.'`

or`'+'`

.`entrance.length == 2`

`0 <= entrance`

_{row}< m`0 <= entrance`

_{col}< n`entrance`

will always be an empty cell.

` ````
```class Solution {
public:
int bfs(vector>& maze, int n, int m, int x, int y)
{
queue> q;
q.push({x,y});
maze[x][y]='+';
int steps=0;
while(!q.empty())
{
int size=q.size();
bool moved=false;
while(size--)
{
int currx=q.front().first;
int curry=q.front().second;
q.pop();
int thisx[]={-1,1,0,0};
int thisy[]={0,0,-1,1};
for(int i=0; i<4; i++)
{
int row=thisx[i]+currx;
int col= thisy[i]+curry;
if(row>=0 and col>=0 and row<=n-1 and col<=m-1 and maze[row][col]=='.')
{
if(row==0 || col==0 || row==n-1 || col==m-1)return steps+1;
maze[row][col]='+';
q.push({row,col});
moved=true;
}
}
}
if(moved)steps++;
}
return -1;
}
int nearestExit(vector>& maze, vector& entrance) {
int n=maze.size();
int m=maze[0].size();
int ans=bfs(maze,n,m,entrance[0],entrance[1]);
return ans;
}
};

660, Sector 14A, Vasundhara, Ghaziabad, Uttar Pradesh - 201012, India