【算法题】BFS：最短路径

BFS（广度优先搜索）是解决无权图/网格/状态空间中最短路径问题的“黄金算法”——其“按层扩散”的核心特性（每一层对应一步距离），保证了第一次到达目标点时的层数就是最短路径长度。这一特性使其在“迷宫最短路径”“基因/单词转换最短步数”“多目标点连续最短路径”等场景中不可替代，是算法面试中最短路径类问题的首选解法。本文通过4道经典最短路径题目（覆盖网格、字符串状态两类场景），拆解BFS解决最短路径的核心框架与场景化适配技巧。

一、迷宫中离入口最近的出口

题目描述：
给定迷宫（'.'表示通路，'+'表示墙）和入口坐标entrance，找到离入口最近的出口（出口定义为迷宫边界上的非入口位置），返回最短步数；若无出口返回-1。

示例：

• 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
• 输出：1（入口(1,2)向右到(1,3)是边界，步数1）

解题思路：
标准层序BFS（每层对应一步）：

1. 初始化队列，入口入队并标记已访问；
2. 按层遍历队列：
   • 每层开始时步数step++（每层对应一步移动）；
   • 遍历当前层所有节点，检查四个方向的邻接节点：
     • 若邻接节点是边界且不是入口，返回当前步数；
     • 若邻接节点是通路且未访问，入队并标记。
3. 遍历结束未找到出口则返回-1。

完整代码：

classSolution{intdx[4]={0,0,1,-1};// 上下左右方向数组intdy[4]={1,-1,0,0};public:intnearestExit(vector<vector<char>>&maze,vector<int>&entrance){intm=maze.size(),n=maze[0].size();vector<vector<bool>>vis(m,vector<bool>(n,false));// 访问标记queue<pair<int,int>>q;// 入口入队并标记q.push({entrance[0],entrance[1]});vis[entrance[0]][entrance[1]]=true;intstep=0;while(!q.empty()){step++;// 每层对应一步，先++再处理intsz=q.size();// 当前层节点数for(inti=0;i<sz;i++){auto[a,b]=q.front();q.pop();// 遍历四个方向for(intj=0;j<4;j++){intx=a+dx[j],y=b+dy[j];// 边界检查 + 未访问 + 通路if(x>=0&&y>=0&&x<m&&y<n&&!vis[x][y]&&maze[x][y]=='.'){// 是边界（出口）则返回步数if(x==0||x==m-1||y==0||y==n-1)returnstep;vis[x][y]=true;q.push({x,y});}}}}return-1;// 无出口}};

复杂度分析：

• 时间复杂度：O(mn)O(mn)O(mn)，每个网格点最多入队一次；
• 空间复杂度：O(mn)O(mn)O(mn)，访问标记数组 + 队列（最坏情况存储所有通路节点）。

二、最小基因变化

题目描述：
基因由8个字符组成（仅包含A/C/G/T），给定起始基因startGene、目标基因endGene和基因库bank，每次只能改变一个字符且改变后的基因必须在基因库中，求从起始到目标的最少变化次数；无法到达返回-1。

示例：

• 输入：startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
• 输出：1（仅改变最后一个字符）

解题思路：
将“基因”视为状态节点，“单字符变化”视为边，转化为状态空间的最短路径问题：

1. 用哈希表存储基因库（快速判断基因是否合法），初始化访问集合；
2. BFS层序遍历：
   • 起始基因入队，标记已访问；
   • 每层对应一次基因变化，遍历当前层所有基因：
     • 遍历每个字符位置，尝试替换为A/C/G/T生成新基因；
     • 若新基因是目标基因，返回当前层数（变化次数）；
     • 若新基因合法且未访问，入队并标记。

完整代码：

classSolution{public:intminMutation(string startGene,string endGene,vector<string>&bank){unordered_set<string>vis;// 访问标记unordered_set<string>hash(bank.begin(),bank.end());// 基因库哈希表string change="ACGT";// 所有可能的基因字符// 边界条件：起始即目标 / 目标不在基因库if(startGene==endGene)return0;if(!hash.count(endGene))return-1;queue<string>q;q.push(startGene);vis.insert(startGene);intret=0;// 变化次数while(!q.empty()){ret++;// 每层对应一次变化intsz=q.size();while(sz--){autot=q.front();q.pop();// 遍历每个字符位置for(inti=0;i<8;i++){autotmp=t;// 临时基因，避免修改原字符串// 尝试替换为4种字符for(intj=0;j<4;j++){tmp[i]=change[j];// 合法且未访问if(!vis.count(tmp)&&hash.count(tmp)){if(tmp==endGene)returnret;// 到达目标vis.insert(tmp);q.push(tmp);}}}}}return-1;// 无法到达}};

复杂度分析：

• 时间复杂度：O(8×4×N)=O(N)O(8×4×N) = O(N)O(8×4×N)=O(N)，N为基因库大小，每个基因最多遍历8个位置×4种字符；
• 空间复杂度：O(N)O(N)O(N)，哈希表 + 队列存储基因状态。

三、单词接龙

题目描述：
给定起始单词beginWord、结束单词endWord和单词列表wordList，每次只能改变一个字符且改变后的单词在列表中，求从起始到结束的最短转换序列长度（序列包含起始单词，如hit→hot→dot→dog→cog长度为5）；无法到达返回0。

示例：

• 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• 输出：5

解题思路：
与“最小基因变化”逻辑一致，差异仅在于：

1. 字符集是26个小写字母（而非4种基因字符）；
2. 序列长度计数：起始单词算1，每层遍历前ret++（最终返回序列长度）。

完整代码：

classSolution{public:intladderLength(string beginWord,string endWord,vector<string>&wordList){unordered_set<string>vis;// 访问标记unordered_set<string>hash(wordList.begin(),wordList.end());// 单词库哈希表// 边界条件：目标不在单词库if(!hash.count(endWord))return0;queue<string>q;q.push(beginWord);vis.insert(beginWord);intret=1;// 序列长度，起始单词算1while(!q.empty()){ret++;// 每层对应一次转换，序列长度+1intsz=q.size();while(sz--){string t=q.front();q.pop();// 遍历每个字符位置for(inti=0;i<t.size();i++){autotmp=t;// 尝试替换为26个字母for(intj=0;j<26;j++){tmp[i]='a'+j;// 合法且未访问if(hash.count(tmp)&&!vis.count(tmp)){if(tmp==endWord)returnret;// 到达目标，返回序列长度q.push(tmp);vis.insert(tmp);}}}}}return0;// 无法到达}};

复杂度分析：

• 时间复杂度：O(L×26×N)O(L×26×N)O(L×26×N)，L为单词长度，N为单词库大小；
• 空间复杂度：O(N)O(N)O(N)，哈希表 + 队列存储单词状态。

四、砍树（多段最短路径拼接）

题目描述：
森林是m×n网格：0是障碍，1是空地，>1的数是树的高度。需要按树高从小到大砍树，从(0,0)出发，每次只能上下左右走，求砍完所有树的最少步数；若某棵树无法到达，返回-1。

示例：

• 输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
• 输出：6（路径：(0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)→(2,0)，共6步）

解题思路：
将“砍树”拆解为多段最短路径问题：

1. 预处理：收集所有树的坐标，按树高从小到大排序；
2. 依次计算“当前位置 → 下一棵要砍的树”的最短路径（BFS）：
   • 累加每段路径的步数；
   • 若某段路径无法到达（返回-1），整体返回-1；
3. 所有树砍完后返回总步数。

完整代码：

classSolution{intm,n;public:intcutOffTree(vector<vector<int>>&forest){m=forest.size(),n=forest[0].size();// 步骤1：收集所有树的坐标vector<pair<int,int>>trees;for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(forest[i][j]>1)trees.push_back({i,j});// 步骤2：按树高从小到大排序sort(trees.begin(),trees.end(),[&](constpair<int,int>p1,constpair<int,int>p2){returnforest[p1.first][p1.second]<forest[p2.first][p2.second];});// 步骤3：依次计算每段最短路径intret=0;intbx=0,by=0;// 当前位置（初始为(0,0)）for(auto&[a,b]:trees){intstep=bfs(forest,bx,by,a,b);if(step==-1)return-1;// 某棵树无法到达ret+=step;bx=a,by=b;// 更新当前位置为刚砍的树}returnret;}// BFS：计算从(bx,by)到(ex,ey)的最短步数，无法到达返回-1intbfs(vector<vector<int>>&forest,intbx,intby,intex,intey){// 起点即终点，步数为0if(bx==ex&&by==ey)return0;intvis[51][51];// 访问标记（网格最大50×50）memset(vis,0,sizeof(vis));// 每次BFS重置标记queue<pair<int,int>>q;q.push({bx,by});vis[bx][by]=1;intstep=0;intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};while(!q.empty()){step++;intsz=q.size();while(sz--){auto[a,b]=q.front();q.pop();for(inti=0;i<4;i++){intx=a+dx[i],y=b+dy[i];// 边界检查 + 未访问 + 非障碍（forest[x][y] != 0）if(x>=0&&y>=0&&x<m&&y<n&&!vis[x][y]&&forest[x][y]){if(x==ex&&y==ey)returnstep;// 到达目标树vis[x][y]=1;q.push({x,y});}}}}return-1;// 无法到达}};

复杂度分析：

• 时间复杂度：O((mn)2)O((mn)^2)O((mn)2)，假设共有K棵树，每棵树的BFS时间为O(mn)O(mn)O(mn)，最坏情况K=mnK=mnK=mn；
• 空间复杂度：O(mn)O(mn)O(mn)，队列 + 访问标记数组。