网站做推广页需要什么,哪些网站是用wordpress,线上营销工具,国展做网站的公司给你一个 m x n 的迷宫矩阵 maze #xff08;下标从 0 开始#xff09;#xff0c;矩阵中有空格子#xff08;用 . 表示#xff09;和墙#xff08;用 表示#xff09;。同时给你迷宫的入口 entrance #xff0c;用 entrance [entrancerow, entrancecol] 表示你一开始…给你一个 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 mmaze[i].length n1 m, n 100maze[i][j] 要么是 . 要么是 。entrance.length 20 entrancerow m0 entrancecol nentrance 一定是空格子。
class Solution {
public:int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int nearestExit(vectorvectorchar maze, vectorint entrance) {int mmaze.size();int nmaze[0].size();queuepairint,int q;bool vis[m][n];memset(vis,0,sizeof vis);q.push({entrance[0],entrance[1]});vis[entrance[0]][entrance[1]]true;int step0;while(q.size()){step;int szq.size();for(int i0;isz;i){auto [a,b]q.front();q.pop();for(int j0;j4;j){int xadx[j],ybdy[j];if(x0xmy0ynmaze[x][y].!vis[x][y]){if(x0||xm-1||y0||yn-1)return step;q.push({x,y});vis[x][y]true;}}}}return -1;}
};
