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

一、问题描述

二、解题思路

由于本题需要求最短路径的长度，所以可以使用bfs来解决这个问题。解题思路如下：

(1)首先，对全局变量进行初始化；

(2)接着，从入口开始进行深度优先搜索，由于本题需要统计的是最小步数，也就是层数，所以需要变量size来记录每一层的节点数，便于统计。如果找到了出口，直接返回step，如果循环执行完了还未找到出口，那就返回-1。

三、代码实现

class Solution { int N,M; vector<vector<bool>> visited; int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; public: int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { //深度优先搜索 //全局变量初始化 N=maze.size(); M=maze[0].size(); visited.resize(N,vector<bool>(M,false)); //BFS queue<pair<int,int>> q; q.push({entrance[0],entrance[1]}); visited[entrance[0]][entrance[1]]=true; int step=0; while(!q.empty()){ step++; int size=q.size();//统计本层的元素数量 while(size--){ pair<int,int> cur=q.front();q.pop(); int cur_x=cur.first; int cur_y=cur.second; for(int i=0;i!=4;i++){ int next_x=cur_x+dx[i]; int next_y=cur_y+dy[i]; if(next_x>=0&&next_x<N&&next_y>=0&&next_y<M&&maze[next_x][next_y]=='.'&&visited[next_x][next_y]==false){ if(next_x==0||next_x==N-1||next_y==0||next_y==M-1) return step; q.push({next_x,next_y}); visited[next_x][next_y]=true; } } } } return -1; } };