今日份题目:
给你一个 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 == 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);}}}// 从入口到不了任意出口,返回-1return -1;}
};
提交结果
欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!
更新不易,宝子们点个赞支持下,谢谢!