《LeetCode 1926 最近出口的迷宫 单源BFS解法》

一.题目1926. 迷宫中离入口最近的出口 - 力扣LeetCode二.思路讲解2.1 本章讲什么本章主要讲解在无权图即每一步移动的代价相同中如何用BFS求解最短路径问题。因为 BFS 具有按层扩散的特性从起点出发第一次访问到某个格子时所经过的步数就是到达该格子的最短距离。因此只要在 BFS 过程中记录当前层的层数一旦遇到满足条件的出口即边界上的空格子且不是入口本身就可以立即返回该层数这就是最近出口的距离。这种思想适用于所有移动代价为 1 的网格搜索问题。2.2 思路讲解对于本题我们可以直接使用 BFS 从入口开始向外逐层探索将入口坐标入队并标记已访问防止走回头路。用变量step记录当前层数初始为 0。当队列不为空时按层处理先记录当前层的大小sz然后循环sz次依次取出队头格子。若当前格子位于迷宫边界且不是入口则返回step因为这是第一次到达边界一定是最短路径。否则向四个方向尝试移动若邻居格子是空格子且未被访问则将其入队并标记。一层处理完后step继续下一层。如果 BFS 结束后仍未找到出口返回 -1。三.代码演示class Solution { public: int bx[4] {0,0,-1,1}; int by[4] {1,-1,0,0}; typedef pairint,intPII; bool check[101][101]; int nearestExit(vectorvectorchar maze, vectorint entrance) { int step 0;//步数 int row maze.size(), col maze[0].size(); int x entrance[0],y entrance[1];//获取起点 queuePIIq; q.push({x,y}); check[x][y] true; while(q.size()) { step; int sz q.size(); for(int i 0;i sz;i) { auto [a,b] q.front(); q.pop(); for(int k 0;k 4;k) { int x a bx[k],y b by[k]; if(x 0 y 0 x row y col !check[x][y] maze[x][y] .) { //如果下一个是出口 if(x 0 || x row - 1 || y 0 || y col - 1) return step; check[x][y] true; q.push({x,y}); } } } } return -1;//没找到出口 } };四.代码讲解一、数据结构与初始化bx[4]、by[4]方向数组表示上下左右四个方向的偏移量顺序不限。check[101][101]布尔数组用于标记格子是否已被访问过防止重复入队。typedef pairint,int PII简化坐标类型的书写。step整型变量记录当前 BFS 的层数即从起点出发已经移动的步数。二、主函数nearestExit获取迷宫尺寸和入口坐标row maze.size(); col maze[0].size();x entrance[0]; y entrance[1];初始化队列将入口坐标入队并标记为已访问check[x][y] true。BFS 层序遍历当队列非空时进入循环表示还有格子可以扩展。step每开始新的一层步数加 1表示从起点出发已经走了step步。int sz q.size();记录当前层的节点个数用于逐层处理。处理当前层所有节点 循环sz次依次取出队头坐标(a, b)。 对每个方向进行探索计算新坐标(x, y) (a bx[k], b by[k])。检查是否合法在网格范围内、未被访问、且是空格子maze[x][y] .。若满足条件则进一步判断如果新格子位于迷宫边界x 0 || x row-1 || y 0 || y col-1则说明找到了一个出口由于 BFS 按层扩散此时step即为最短步数直接返回step。否则将新格子标记为已访问并加入队列供下一层探索。循环结束若 BFS 结束后仍未返回说明没有可到达的出口返回-1。三、关键细节BFS 的层序性质BFS 第一次访问到某个格子时所用的步数就是最短距离。因此只要在扩展过程中遇到边界格子立即返回当前层数step保证结果是最小值。步数递增时机step放在每层开始之前表示进入下一层这样第一次扩展到的出口对应的步数就是正确的。入口不算出口代码在扩展时只检查新格子是否为边界且入口已经在初始时标记为已访问因此不会将入口本身误判为出口。五、流程图