BFS算法篇——穿越迷雾森林，探幽最短路径之谜（下）

用户11379153

发布于 2025-11-05 16:28:08

1080

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

引言

上篇我们介绍了bfs算法求取最短路径的应用场景和代码实现，本篇将结合具体题目，进一步深化对其的理解运用。

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

1.1 题目链接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/

1.2 题目分析：

给定mxn的矩阵，表示迷宫
矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）
用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列，即入口
每次可以上下左右方向移动一次，要求返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

1.3 思路讲解：

同样是事先的准备工作，int dx[]和int dy[]分别表示方向，根据迷宫大小建立标记数组，step记录总步数。

根据entran数组找到起点坐标，在vis中标记为true。
将起点入队列，开始bfs上下左右四个方向进行遍历，如果可以通行，则将该节点入队列，否则跳过该节点继续遍历
每一层遍历，代表步数+1
出口的判断即为边界情况，如果遍历到了出口，直接返回step接口
如果遍历所有节点仍未返回，说明不存在合法路径出口，返回-1

1.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int step=0;
    bool vis[101][101]={false};//标记数组
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m=maze.size(),n=maze[0].size();
        queue<pair<int,int>> q;
        q.push({entrance[0],entrance[1]});//起点入队列
        vis[entrance[0]][entrance[1]]=true;
        while(q.size())
        {
            step++;
            int sz=q.size();
            for(int i=0;i<sz;i++)
            {
                auto [a,b]=q.front();
                q.pop();
                vis[a][b]=true;
                //下一层入队列
                for(int j=0;j<4;j++)
                {
                    int x=a+dx[j],y=b+dy[j];

                    //判断是否可以前进
                    if(x>=0 && x<m && y>=0 && y<n && maze[x][y]=='.' && vis[x][y]==false)
                    {
                        //判断是否为出口
                        if(x==0 || x==m-1 || y==0 || y==n-1)
                        {
                            return step;
                        }
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;

        
    }
};

二、最小基因变化

2.1 题目链接：https://leetcode.cn/problems/minimum-genetic-mutation/description/

2.2 题目分析：

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
一次基因变化就意味着这个基因序列中的一个字符发生了变化。

注意: start基因可能不在基因库内，如果start不在，则直接返回-1即可。

2.3 思路讲解：

首先我们需要考虑特殊情况：

start不在bank内
end不在bank内

那么这种情况直接返回-1即可

基因变化与之前迷宫问题的上下左右类似，只不过在这里是A,G,C,T

我们仍然可以沿用层序遍历的思路，将start入队列，ret作为最终返回次数，每层进行遍历判断。，ret++
在遍历时需要更新标记数组，同时，要注意不能污染源字符串
如果变化后的字符串在bank内且未出现过，则入队列
变化后的字符串与end相等时，直接返回ret即可，因此需要在循环最开始ret++
遍历结束时若仍未返回，说明不存在，直接返回-1即可

2.4 代码实现：

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> hash(bank.begin(),bank.end());
        unordered_set<string> vis;//标记数组
        string change="ACGT";//基因变化
        int ret=0;//变化次数
        //处理特殊情况
        if(startGene==endGene)
        {
            return 0;
        }
        if(!hash.count(endGene))
        {
            return -1;
        }
        queue<string> q;
        q.push(startGene);//起始基因入队列
        vis.insert(startGene);
        while(q.size())
        {
            ret++;//更新次数
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                for(int i=0;i<8;i++)//8个字符逐个遍历
                {
                    
                    for(int j=0;j<4;j++)
                    {
                        string temp=t;//避免污染源字符串
                        temp[i]=change[j];//字符变换
                        if(temp==endGene)
                        {
                            return ret;
                        }//判断是否相等
                        if(hash.count(temp) && !vis.count(temp))
                        {
                            q.push(temp);
                            vis.insert(temp);
                        }

                    }
                }
            }
        }
        return -1;
    }
};

三、单词接龙

3.1 题目链接：https://leetcode.cn/problems/word-ladder/description/

3.2 题目分析：

与上题基因变化基本同理，只是每次变化由AGCT变为了任意一个字符

3.3 思路讲解：

与上题基本同理，不再赘述。

3.4 代码实现：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vis;//标记数组
        unordered_set<string> hash(wordList.begin(),wordList.end());
        //处理特殊情况
        if(!hash.count(endWord))
        {
            return 0;
        }
        int ret=1;//返回长度
        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);
        while(q.size())
        {
            ret++;//每层长度+1
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                int m=t.size();//该单词长度
                for(int i=0;i<m;i++)
                {
                    
                    for(char ch='a';ch<='z';ch++)
                    {
                       string temp=t;//避免污染源字符串
                        temp[i]=ch;
                        if(temp==endWord)
                        {
                            return ret;
                        }//成功情况
                        if(temp!=endWord && hash.count(temp) && !vis.count(temp))
                        {
                            vis.insert(temp);
                            q.push(temp);
                        }
                    }
                }
            }
        }
        return 0;
        
    }
};

四、为高尔夫比赛砍树

4.1 题目链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/

4.2 题目分析：

给定树林由一个 m x n 的矩阵表示，在这个矩阵中：

0 表示障碍，无法触碰 1 表示地面，可以行走比 1 大的数表示有树的单元格，可以行走，数值表示树的高度

每次可以上下左右进行一次移动，如果移动后的位置有树，需要决定是否砍掉他，且砍完后该位置变为地面
砍树必须按照高度由低到高进行
最终返回最小步数，如果无法砍完所有树，则返回0

4.3 思路讲解

首先仍然是准备工作，dx[],dy[],标记数组vis。由于本题要求砍树高度从低到高进行，因此，我们还需要一个数组记录排序后树的下标

在将砍树顺序依次记录后，便可以从起点(0,0）开始，依次上下左右遍历
本题由于遍历顺序已经指定，可以另外再专门写一个由A->B最小步数的bfs，进行步数累加记录

4.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;//数组规模
    int ret=0;//最终步数
    bool vis[51][51];//标记数组
    int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey)
    {
        queue<pair<int,int>> q;
        int step=0;//步数
        memset(vis,0,sizeof(vis));//重置清零操作
        //处理特殊情况
        if(bx==ex && by==ey)
        {
            return 0;
        }
        q.push({bx,by});//起点入队列
        vis[bx][by]=true;//更新标记
        while(q.size())
        {
            int sz=q.size();
            step++;
            while(sz--)
            {
                auto [a,b]=q.front();
                q.pop();
                for(int i=0;i<4;i++)
                {
                    int x=a+dx[i],y=b+dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false &&forest[x][y])
                    {
                    if (x == ex && y == ey)
                    {
                        return step;
                    }//成功情况
                    q.push({x,y});
                    vis[x][y]=true;
                    }

                }
            }
        }
        return -1;//未成功找到

    }
    int cutOffTree(vector<vector<int>>& forest) {
        m=forest.size(),n=forest[0].size();
        vector<pair<int,int>> trees;
        //存储树节点
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(forest[i][j]>1)
                {
                    trees.push_back({i,j});
                }
            }
        }
        //排序
        sort(trees.begin(),trees.end(),[&](const pair<int,int>& a,const pair<int,int>& b)
        {
            return forest[a.first][a.second]<forest[b.first][b.second];
        });
        int bx=0,by=0;//起点
        for(auto& [a,b] :trees)
        {
            int temp=bfs(forest,bx,by,a,b);
            if(temp==-1)
            {
                return -1;
            }//无法砍完所有的树
            ret+=temp;//累加
            bx=a,by=b;//更新起点
        }
        return ret;

        
    }
};