1926 迷宫中离入口最近的出口

题目描述：
给你一个 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 一定是空格子。

方法1:
主要思路：解题链接汇总
（1）常规的广度优先方法；

class Solution {
public:bool check(int r,int c,int m,int n){if(r==0||c==0||r==m-1||c==n-1){return true;}return false;}int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int step=1;int cur_size=1;queue<vector<int>> q;q.push(entrance);maze[entrance[0]][entrance[1]]='+';while(!q.empty()){cur_size=q.size();while(cur_size--){vector<int>tmp=q.front();q.pop();if(tmp[0]-1>=0&&maze[tmp[0]-1][tmp[1]]=='.'){if(check(tmp[0]-1,tmp[1],maze.size(),maze[0].size())){return step;}maze[tmp[0]-1][tmp[1]]='+';q.push({tmp[0]-1,tmp[1]});}if(tmp[0]+1<maze.size()&&maze[tmp[0]+1][tmp[1]]=='.'){if(check(tmp[0]+1,tmp[1],maze.size(),maze[0].size())){return step;}maze[tmp[0]+1][tmp[1]]='+';q.push({tmp[0]+1,tmp[1]});}if(tmp[1]-1>=0&&maze[tmp[0]][tmp[1]-1]=='.'){if(check(tmp[0],tmp[1]-1,maze.size(),maze[0].size())){return step;}maze[tmp[0]][tmp[1]-1]='+';q.push({tmp[0],tmp[1]-1});}if(tmp[1]+1<maze[0].size()&&maze[tmp[0]][tmp[1]+1]=='.'){if(check(tmp[0],tmp[1]+1,maze.size(),maze[0].size())){return step;}maze[tmp[0]][tmp[1]+1]='+';q.push({tmp[0],tmp[1]+1});}}++step;}return -1;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！