5793. 迷宫中离入口最近的出口

# 题目

## 5793. 迷宫中离入口最近的出口

[https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze/](https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze/)

给你一个 `m x n` 的迷宫矩阵 `maze` （**下标从 0 开始**），矩阵中有空格子（用 `'.'` 表示）和墙（用 `'+'` 表示）。同时给你迷宫的入口 `entrance` ，用 `entrance = [entrancerow, entrancecol]` 表示你一开始所在格子的行和列。

每一步操作，你可以往 **上**，**下**，**左** 或者 **右** 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 `entrance` **最近** 的出口。**出口** 的含义是 `maze` **边界** 上的 **空格子**。`entrance` 格子 **不算** 出口。

请你返回从 `entrance` 到最近出口的最短路径的 **步数** ，如果不存在这样的路径，请你返回 `-1` 。

**示例 1：**

![img](https://img.czbiao.com/img/202107/11/20210711003429.jpeg)

```
输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。
```

**示例 2：**

![img](https://img.czbiao.com/img/202107/11/20210711003425.jpeg)

```
输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。
```

**示例 3：**

![img](https://img.czbiao.com/img/202107/11/20210711003439.jpeg)

```
输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。
```

**提示：**

- `maze.length == m`
- `maze[i].length == n`
- `1 <= m, n <= 100`
- `maze[i][j]` 要么是 `'.'` ，要么是 `'+'` 。
- `entrance.length == 2`
- `0 <= entrancerow < m`
- `0 <= entrancecol < n`
- `entrance` 一定是空格子。

# 题解

## 思路

bfs搜索，标记已经走过的节点，对特殊值做判断。写的时候判断边界有点问题，索性当前值放进hash，执行上下左右。

## 代码

```javascript
/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function (maze, entrance) {
    function bfs(line, low) {
        const arr = [];
        // hash记录走过的节点
        const hash = new Set();
        let [i, j] = entrance;
        hash.add(`${i}-${j}`);
        arr.push([i + 1, j]);
        arr.push([i - 1, j]);
        arr.push([i, j + 1]);
        arr.push([i, j - 1]);
        let step = 1;
        while (arr.length) {
            length = arr.length;
            for (let k = 0; k < length; k++) {
                data = arr.shift();
                [i, j] = data;
                // 超过边界
                if (i < 0 || j < 0 || i >= line || j >= low) {
                    continue;
                }
                // 是墙或者出现过
                if (maze[i][j] === '+' || hash.has(`${i}-${j}`)) {
                    continue;
                }
                // 等于出口则返回
                if (i === 0 || j === 0 || i === line - 1 || j === low - 1) {
                    return step;
                }
                // 上下左右移动
                arr.push([i + 1, j]);
                arr.push([i - 1, j]);
                arr.push([i, j + 1]);
                arr.push([i, j - 1]);
                // 记录走过的节点
                hash.add(`${i}-${j}`);
            }
            step++;
        }
        return -1;
    }

return bfs(maze.length, maze[0].length);
};
```