迷宫中离入口最近的出口
题目来源：Leetcode1926. 迷宫中离入口最近的出口
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
算法原理：
本题就是边权为1的最短路问题，对于此例子而言小人要么从上走一步，要么从左走两步，到达边界。
解决办法就是在起点用BFS，一层一层往外扩，当扩展到边界情况就返回层数。
为防止遍历过程中有的位置重复遍历，我们要用一个Bool数组来进行记录。
代码实现：
class Solution { int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; public: int nearestExit(vector<vector<char>>& maze, vector<int>& e) { int m=maze.size(),n=maze[0].size(); bool vis[m][n]; memset(vis,0,sizeof vis); queue<pair<int,int>> q; q.push({e[0],e[1]}); vis[e[0]][e[1]]=true; //记录层数 int step=0; while(q.size()) { step++; int sz=q.size(); for(int i=0;i<sz;i++) { auto [a,b]=q.front(); q.pop(); for(int j=0;j<4;j++) { int x=a+dx[j],y=b+dy[j]; //防止越界 if(x>=0&&x<m&&y>=0&&y<n&&maze[x][y]=='.'&&vis[x][y]==false) { //判断是否已经到达出口 if(x==0||x==m-1||y==0||y==n-1) return step; q.push({x,y}); vis[x][y]=true; } } } } return -1; } };
