在线设计网站免费,直播是网站怎么做,网站描述怎么修改吗,做网站建设很赚钱吗今日份题目#xff1a;
给你一个 m x n 的迷宫矩阵 maze #xff08;下标从 0 开始#xff09;#xff0c;矩阵中有空格子#xff08;用 . 表示#xff09;和墙#xff08;用 表示#xff09;。同时给你迷宫的入口 entrance #xff0c;用 entrance [entrancerow, …今日份题目
给你一个 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,pairint,int 要用queuetupleint,int,int
其次将某点加入队列后一定要将这个点设置为墙我刚开始没有注意到这点就导致点上下上下一直循环或者麻烦点用另一个数组标记到达过的点否则会陷入死循环
最后我刚开始想用p.push_back({d1{nx,ny}})发现报错最后学到要用p.emplace(d1,nx,ny)注意emplace括号里没有大括号。
代码
class Solution
{
public:int nearestExit(vectorvectorchar maze, vectorint entrance) {int nmaze.size();int mmaze[0].size();// 上下左右四个方向int dx[4]{-1,1,0,0};int dy[4]{0,0,-1,1};queuetupleint,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 i0;i4;i){// 获取四周的新坐标int nxxdx[i];int nyydy[i];// 新坐标合法且不为墙if(nx0nxnny0nymmaze[nx][ny].){if(nx0||nxn-1||ny0||nym-1) //到达边界了{// 新坐标为出口返回距离作为答案return d1;}// 修改为墙并加入队列maze[nx][ny]; //注意不修改为墙会走回来p.emplace(d1,nx,ny);}}}// 从入口到不了任意出口返回-1return -1;}
};提交结果 欢迎大家在评论区讨论如有不懂的部分欢迎在评论区留言
更新不易宝子们点个赞支持下谢谢
