企业官网建设流程全解析

一.题目

1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

二.思路讲解

2.1 本章讲什么

本章主要讲解在无权图（即每一步移动的代价相同）中，如何用BFS求解最短路径问题。

• 因为 BFS 具有按层扩散的特性，从起点出发，第一次访问到某个格子时所经过的步数，就是到达该格子的最短距离。

• 因此，只要在 BFS 过程中记录当前层的层数，一旦遇到满足条件的出口（即边界上的空格子，且不是入口本身），就可以立即返回该层数，这就是最近出口的距离。

• 这种思想适用于所有移动代价为 1 的网格搜索问题。

2.2 思路讲解

对于本题，我们可以直接使用 BFS 从入口开始向外逐层探索：

1. 将入口坐标入队，并标记已访问（防止走回头路）。

2. 用变量step记录当前层数（初始为 0）。

3. 当队列不为空时，按层处理：先记录当前层的大小sz，然后循环sz次，依次取出队头格子。

   • 若当前格子位于迷宫边界（且不是入口），则返回step（因为这是第一次到达边界，一定是最短路径）。

   • 否则，向四个方向尝试移动，若邻居格子是空格子且未被访问，则将其入队并标记。

4. 一层处理完后，step++，继续下一层。

5. 如果 BFS 结束后仍未找到出口，返回 -1。

三.代码演示

class Solution { public: int bx[4] = {0,0,-1,1}; int by[4] = {1,-1,0,0}; typedef pair<int,int>PII; bool check[101][101]; int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { int step = 0;//步数 int row = maze.size(), col = maze[0].size(); int x = entrance[0],y = entrance[1];//获取起点 queue<PII>q; 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 pair<int,int> PII：简化坐标类型的书写。

• step：整型变量，记录当前 BFS 的层数（即从起点出发已经移动的步数）。

二、主函数nearestExit

1. 获取迷宫尺寸和入口坐标：row = maze.size(); col = maze[0].size();x = entrance[0]; y = entrance[1];

2. 初始化队列：将入口坐标入队，并标记为已访问（check[x][y] = true）。

3. BFS 层序遍历：

   • 当队列非空时，进入循环，表示还有格子可以扩展。

   • step++：每开始新的一层，步数加 1，表示从起点出发已经走了step步。

   • int sz = q.size();：记录当前层的节点个数，用于逐层处理。

4. 处理当前层所有节点： 循环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。

     • 否则，将新格子标记为已访问，并加入队列，供下一层探索。

5. 循环结束：若 BFS 结束后仍未返回，说明没有可到达的出口，返回-1。

三、关键细节

• BFS 的层序性质：BFS 第一次访问到某个格子时，所用的步数就是最短距离。因此，只要在扩展过程中遇到边界格子，立即返回当前层数step，保证结果是最小值。

• 步数递增时机：step++放在每层开始之前，表示进入下一层，这样第一次扩展到的出口对应的步数就是正确的。

• 入口不算出口：代码在扩展时只检查新格子是否为边界，且入口已经在初始时标记为已访问，因此不会将入口本身误判为出口。

五、流程图