Formatted question description: https://leetcode.ca/all/1926.html

# 1926. Nearest Exit from Entrance in Maze

## Level

Medium

## Description

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_row, entrance_col]`

denotes the row and column of the cell you are initially standing at.

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 to the nearest exit, or -1 if no such path exists*.

**Example 1:**

**Input:** maze = [[”+”,”+”,”.”,”+”],[”.”,”.”,”.”,”+”],[”+”,”+”,”+”,”.”]], entrance = [1,2]

**Output:** 1

**Explanation:** 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:** 2

**Explanation:** 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:** -1

**Explanation:** 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.

## Solution

Do breadth-first search in `maze`

starting from `entrance`

. The cell `entrance`

is visited first and does not count as an exit. Once the first empty cell that is on the border is visited, return the number of steps.

```
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int m = maze.length, n = maze[0].length;
boolean[][] visited = new boolean[m][n];
visited[entrance[0]][entrance[1]] = true;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(entrance);
int steps = 0;
while (!queue.isEmpty()) {
steps++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
int row = cell[0], column = cell[1];
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n && !visited[newRow][newColumn] && maze[newRow][newColumn] == '.') {
if (newRow == 0 || newRow == m - 1 || newColumn == 0 || newColumn == n - 1)
return steps;
visited[newRow][newColumn] = true;
queue.offer(new int[]{newRow, newColumn});
}
}
}
}
return -1;
}
}
```