每天一道leetcode：1926. 迷宫中离入口最近的出口（图论&中等&广度优先遍历）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每天一道leetcode：1926. 迷宫中离入口最近的出口（图论&中等&广度优先遍历）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今日份题目：

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

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

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

示例1

每天一道leetcode：1926. 迷宫中离入口最近的出口（图论&中等&广度优先遍历）,图论,leetcode,图论,职场和发展,算法,广度优先,c++,数据结构

输入：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

每天一道leetcode：1926. 迷宫中离入口最近的出口（图论&中等&广度优先遍历）,图论,leetcode,图论,职场和发展,算法,广度优先,c++,数据结构

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

示例3

每天一道leetcode：1926. 迷宫中离入口最近的出口（图论&中等&广度优先遍历）,图论,leetcode,图论,职场和发展,算法,广度优先,c++,数据结构

输入：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 一定是空格子。

题目思路

使用广度优先遍历，和之前的做法一样，用一个队列存放下个可以到达的位置信息，这里我就说一下重点要注意的地方和我踩的坑：

首先，需要一个额外的int型变量存放距离，不能用queue< <int,pair<int,int> > >，要用queue<tuple<int,int,int> >；

其次，将某点加入队列后一定要将这个点设置为墙，我刚开始没有注意到这点，就导致点上下上下一直循环，或者麻烦点用另一个数组标记到达过的点，否则会陷入死循环；

最后，我刚开始想用p.push_back({d+1{nx,ny}})，发现报错，最后学到要用p.emplace(d+1,nx,ny)，注意emplace括号里没有大括号。

代码

class Solution 
{
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        int n=maze.size();
        int m=maze[0].size();
        // 上下左右四个方向
        int dx[4]={-1,1,0,0};
        int dy[4]={0,0,-1,1};
        queue<tuple<int,int,int> > p;
        // 入口加入队列
        p.emplace(0,entrance[0],entrance[1]);
        // 入口修改为墙，这样就不用额外考虑入口在边界的情况了
        maze[entrance[0]][entrance[1]]='+';
        while(!p.empty())
        {
            // 获取当前位置的坐标
            auto [d,x,y]=p.front();
            p.pop();
            // 遍历四个方向的格子
            for(int i=0;i<4;i++)
            {
                // 获取四周的新坐标
                int nx=x+dx[i];
                int ny=y+dy[i];
                // 新坐标合法且不为墙
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]=='.')
                {
                    if(nx==0||nx==n-1||ny==0||ny==m-1) //到达边界了
                    {
                        // 新坐标为出口，返回距离作为答案
                        return d+1;
                    }
                    // 修改为墙并加入队列
                    maze[nx][ny]='+'; //注意，不修改为墙会走回来
                    p.emplace(d+1,nx,ny);
                }
            }
        }
        // 从入口到不了任意出口，返回-1
        return -1;
    }
};