给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
示例 1：
输入：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：
输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。示例 3：
输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。提示：
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j]要么是'.'，要么是'+'。entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance一定是空格子。
解题思路：广度优先遍历
其实这类最短路径问题，和前面的 floodfill 算法问题是差不多的，大体代码框架还是那样子！
这道题无非就是给定一个起点，然后找出从起点到边界的权值总和最小的路径，而每一步的权值是 1。所以我们可以用一个变量 step 记录下路径长度，从起点做一个广度优先遍历，将其临近的并且符合要求的节点添加到队列中，此时判断一下如果这些节点中如果就是边界节点的话，则直接返回 step，如果不是的话则继续做广度优先遍历。
如果最后都没找到边界节点的话，说明没有出口，则直接返回 -1。
然后在 bfs 途中和 floodfill 算法不同的是，我们要将每一层队列中的节点拎出来做 bfs，也就是每一层队列有 size 个，则对这层做 size 次 bfs，而不是不停的做 bfs，因为我们要控制一层一层往外走，就得控制每次操作的是一层的节点，就像二叉树的层序遍历一样。
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size(), n = maze[0].size();
// 将起点加入到队列中
queue<pair<int, int>> bfs;
bfs.push({entrance[0], entrance[1]});
maze[entrance[0]][entrance[1]] = '+';
int step = 0;
while(!bfs.empty())
{
step++; // 每一层广度就让step++
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
if(newx >= 0 && newy >= 0 && newx < m && newy < n && maze[newx][newy] == '.')
{
// 如果遇到了出口，此时就是最短路径了，直接返回step即可
if(newx == 0 || newx == m - 1 || newy == 0 || newy == n - 1)
return step;
bfs.push({newx, newy});
maze[newx][newy] = '+';
}
}
}
}
return -1; // 如果没找到出口的话，则返回-1
}
};