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

一、问题描述二、解题思路由于本题需要求最短路径的长度所以可以使用bfs来解决这个问题。解题思路如下(1)首先对全局变量进行初始化(2)接着从入口开始进行深度优先搜索由于本题需要统计的是最小步数也就是层数所以需要变量size来记录每一层的节点数便于统计。如果找到了出口直接返回step如果循环执行完了还未找到出口那就返回-1。三、代码实现class Solution { int N,M; vectorvectorbool visited; int dx[4]{0,1,0,-1}; int dy[4]{-1,0,1,0}; public: int nearestExit(vectorvectorchar maze, vectorint entrance) { //深度优先搜索 //全局变量初始化 Nmaze.size(); Mmaze[0].size(); visited.resize(N,vectorbool(M,false)); //BFS queuepairint,int q; q.push({entrance[0],entrance[1]}); visited[entrance[0]][entrance[1]]true; int step0; while(!q.empty()){ step; int sizeq.size();//统计本层的元素数量 while(size--){ pairint,int curq.front();q.pop(); int cur_xcur.first; int cur_ycur.second; for(int i0;i!4;i){ int next_xcur_xdx[i]; int next_ycur_ydy[i]; if(next_x0next_xNnext_y0next_yMmaze[next_x][next_y].visited[next_x][next_y]false){ if(next_x0||next_xN-1||next_y0||next_yM-1) return step; q.push({next_x,next_y}); visited[next_x][next_y]true; } } } } return -1; } };