1926.Nearest Exit from Entrance in Maze
===
###### tags: `Medium`,`BFS`,`Matrix`,`Array`
[1926. Nearest Exit from Entrance in Maze](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/)

### 題目描述：
走迷宮，找最近的出口。

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.

### 範例：


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

Output: 1

### 解答

#### Javascript

function nearestExit(maze, entrance) {
  const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0;
  const isExit = (x, y, xLength, yLength) => x === 0 || x === xLength - 1 || y === 0 || y === yLength - 1;
  const queue = [[entrance[0], entrance[1], 0]];
  const visited = [];
  for (let i = 0; i < maze.length; i++) {
    visited[i] = [];
    for (let j = 0; j < maze[i].length; j++) {
      visited[i][j] = false;
    }
  }
  visited[entrance[0]][entrance[1]] = true;

  // BFS
  while (queue.length) {
    const [x, y, step] = queue.shift();
    const neighbors = [
      [x + 1, y],
      [x - 1, y],
      [x, y + 1],
      [x, y - 1],
    ];
    for (const neighbor of neighbors) {
      if (!isInBounds(neighbor[0], neighbor[1], maze.length, maze[0].length)) continue;
      if (maze[neighbor[0]][neighbor[1]] === '.' && !visited[neighbor[0]][neighbor[1]]) {
        if (isExit(neighbor[0], neighbor[1], maze.length, maze[0].length)) return step + 1;
        queue.push([neighbor[0], neighbor[1], step + 1]);
      }
      visited[neighbor[0]][neighbor[1]] = true;
    }
  }

  return -1;
}

> [name=Marsgoat] [time= Nov 21, 2022]

#### C++

int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int res = 0;
int row_n = maze.size(), col_n = maze[0].size();

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> thisLevel = {entrance};
maze[entrance[0]][entrance[1]] = '+';
while(!thisLevel.empty())
{
    vector<vector<int>> nextLevel;
    for(auto& v : thisLevel)
    {
        int row = v[0], col = v[1];                
        for(auto& d : dirs)
        {
            int next_row = row+d[0], next_col = col+d[1];
            if(next_row >= row_n || next_row < 0 || next_col >= col_n || next_col < 0 || maze[next_row][next_col] == '+')
                continue;
            if(next_row == 0 || next_row == row_n-1 || next_col == 0 || next_col == col_n-1)
                return res+1;
            maze[next_row][next_col] = '+';
            nextLevel.push_back({next_row, next_col});
        }                
    }
    res++;
    thisLevel=nextLevel;
}
return -1;
}

> [name=XD] [time= Nov 21, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)