BFS算法——层层推进，最短之路，广度优先搜索算法的诗意旅程（下）

引言

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

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

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

1.2 题目分析：

• 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。
• 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
• 可以上下左右在空格子内进行移动，无法穿过墙，要求寻找距离入口最近的出口
• 每移动一次视为移动一步，求出最短步数

1.3 思路讲解：

利用层序遍历的思想，一层则可视为一步，其余步骤与上题基本相同。
注意处理边界情况！！！

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内的一个字符进行A，C，G，T的变化
• 每次变化后的序列都要在bank中，求取最少变化次数
• 若无法变化成功，则返回-1

2.3 思路讲解：

首先考虑特殊情况：

• 如果start==end，说明无须变化，直接返回次数0
• 如果end不在bank内，说明不可能变化成功，直接返回-1

由于每次变化只能在ACGT的范围内，因此我们可以先定义一个string change=ACGT，类比之前变化时的数组dx和dy

• 根据之前讲解的BFS思想，我们考虑创建一个标记数组vis，以及hash来判断变化后的字符串temp是否处于bank内。
• 之后创建一个队列，将start序列入队列，根据层序遍历，每次对其进行ACGT的变化，因此一层就相当于变化一次，记录变化次数ret
• 如果变化后的序列与end相等且在bank内，则说明变化成功，直接返回ret
• 如果不相等且temp处于bank内，则将变化后的序列及录入vis内，避免重复判断

2.4 代码实现：

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis;//标记数组
        unordered_set<string> hash(bank.begin(),bank.end());
        //处理特殊情况
        if(startGene==endGene) return 0;
        if(!hash.count(endGene)) return -1;
        string change="ACGT";//每次的变化序列
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int ret=0;//变化次数
        while(q.size())
        {
            ret++;//每层次数加1
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                for(int i=0;i<8;i++)
                {
                     string temp=t;//避免污染源字符串
                for(int j=0;j<4;j++)
                {
                   
                    temp[i]=change[j];
                    if(temp==endGene && hash.count(endGene))
                    {
                        return ret;
                    }//成功情况
                    if(temp!=endGene && hash.count(temp) && !vis.count(temp))
                    {
                        vis.insert(temp);
                        q.push(temp);
                    }
                }
                }
            }

        }
        return -1;


        
    }
};

三. 单词接龙

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

3.2 题目分析：

本题与上题基因变化类似，都是给出start与end，每次变化一个字母，求最小变化次数

• 每次变化一个字母后，字符串temp必须在给定的数组wordlist内
• 如果无法成功变化为end，则返回0

3.3 思路讲解：

首先考虑特殊情况：

• 如果end不在wordlist内，无论如何也无法成功变化，因此直接返回0

剩余思路与上题完全一致，只需要将遍历方向改为26个字符a->z即可。

注意本题要返回的是长度，start也算一个字符串，因此要在最小变化次数的基础上再加1

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*n的矩阵，其中

• 0表示障碍，无法行走
• 1表示地面，可以通行
• 大于1的数表示该处存在一棵树，且值的大小为树的高度，可以通行

要求从(0,0)开始，按照树的高度从低到高砍完所有树,且每次砍树之后，该处变为1

返回砍完所有树所需的最小步数

如果无法砍完所有树，则返回-1

4.3 思路讲解：

首先我们需要明确，只有遇到0时，才无法通行

• m*n的矩阵可以类比之前的迷宫问题，定义dx和dy数组，进行方向上的移动
• 遍历矩阵，按照树的高度由低到高用数组trees存储树节点

由于题目要求从低到高进行砍树，因此本题就转化为遍历trees，求两两相邻节点的最小步数之和。

求取两个点的最短路径，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;

        
    }
};

小结

本篇关于bfs算法求取最短路径的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！