【优选算法专栏】专题十六：BFS解决最短路问题（一）

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

迷宫中离入口最近的出口

题目来源：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;
    }
};