自学内容网 自学内容网

【算法】BFS 系列之边权为 1 的最短路问题

【ps】本篇有 4 道 leetcode OJ。 

目录

一、算法简介

二、相关例题

1)迷宫中离入口最近的出口

.1- 题目解析

.2- 代码编写

2)最小基因变化

.1- 题目解析

.2- 代码编写

3)单词接龙

.1- 题目解析

.2- 代码编写

4)为高尔夫比赛砍树

.1- 题目解析

.2- 代码编写


一、算法简介

        最短路问题是图论中一种经典的题型,包括单源最短路、多源最短路、边权为 1 的最短路等等。本篇主要讲述的是边权为 1 的最短路问题。

        有如下一幅无向图,其中的每个点都可以看作是一个地点,两点之间的线可以看作是一条路径,路径上标识的权值(边权)可以看作是路径的长度,所谓最短路问题,就是求一个地点到另一个地点的最短路径长度。

         而边权为 1 的最短路问题,就是指每条路径上的权值都为 1 或都相同。

        对于这类问题,通常是借助 BFS,结合哈希表来得出一个最优解,其中,BFS 通过模拟一个队列的入队和出队来完成,而哈希表用来标识某一个地点是否已经遍历过。

        之所以能用 BFS 得到最优解,是因为在入队和出队的过程中,一定会有一次层序遍历比另一次先到达某个地点。例如下图中,A到达E有两条路径,但由于边权为 1,A->C->E 一定比 A->B->D->E 更短,且由于 BFS 是层序遍历的,从 A 点同时出发,一层一层向外扩展的,因此 E 点一定和 D 点同时入队,此时 A->C->E 已经走完了,A->B->D->E 才走到 D 还没走到 E,因此在进行 BFS 时,是能够区分最短路径,能够找到最优解的。

        而最短路径其实就是,从起点到终点进行 BFS 时所扩展的层数。

 

二、相关例题

1)迷宫中离入口最近的出口

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

 

.1- 题目解析

        如果把小人最初所在的位置当作是一个地点,两个格子之间是一条长度为 1 的路径,那么这道题就可以抽象成是边权为 1 的最短路问题。

        我们直接使用 BFS 遍历路径和地点即可。 

.2- 代码编写

class Solution {
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
        int m=maze.size(),n=maze[0].size();
        bool vis[m][n];    //记录地点是否被遍历过
        memset(vis,0,sizeof(vis));

        queue<pair<int,int>> q;//通过队列的入队和出队来实现BFS
        q.push({e[0],e[1]});
        vis[e[0]][e[1]]=true;

        int step=0; //记录扩展的层数
        while(q.size())
        {
            step++;//每次向外扩展一层都要记录
            int sz=q.size();//每次取队长,方便出队
            for(int i=0;i<sz;i++)
            {
                auto [a,b]=q.front();q.pop();
                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])
                    {
                        if( x==0 ||x==m-1 || y==0 || y==n-1) //扩展到矩阵边界,则可返回了
                            return step;
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
};

2)最小基因变化

433. 最小基因变化

 

.1- 题目解析

        字符串 AAAA 可以变化成 CAAA、GAAA、TAAA 等等,如果将这些字符串看作是一个地点,那么由一个字符串变化成另一个字符串的过程,就可以抽象成是边权为 1 的最短路问题。

.2- 代码编写

class Solution {
public:
    int minMutation(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) //变化前后相等
            return 0;
        if(!hash.count(endGene)) //基因库里不存在
            return -1;
        
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);

        int ret=0;//记录扩展的层数
        while(q.size())
        {
            ret++;
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                //暴力枚举所有可变的字符组合
                for(int i=0;i<8;i++)//遍历原字符组合
                {
                    string tmp=t;//细节问题
                    for(int j=0;j<4;j++)//遍历可变化的字符
                    {
                        tmp[i]=change[j];
                        if(hash.count(tmp)&&!vis.count(tmp))//当前枚举的一种字符组合在基因库中存在
                        {
                            if(tmp==endGene) //若已枚举出最终结果,则直接返回
                                return ret;
                            q.push(tmp);    //否则继续BFS枚举字符组合
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};

3)单词接龙

127. 单词接龙

 

.1- 题目解析

        本题与上一道题几乎一模一样,也可以将符串看作是一个地点,将一个字符串变化成另一个字符串的过程抽象成是边权为 1 的最短路问题。

.2- 代码编写

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(),wordList.end());
        unordered_set<string> vis;

        if(!hash.count(endWord))return 0;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int ret=1;//统计一共有多少个单词
        while(q.size())
        {
            ret++;
            int sz=q.size();
            while(sz--)
            {
                string t=q.front();
                q.pop();
                //暴力枚举所有可变化的字符组合
                for(int i=0;i<t.size();i++)
                {
                    string tmp=t;
                    for(char ch='a';ch<='z';ch++)
                    {
                        tmp[i]=ch;
                        if(hash.count(tmp) && !vis.count(tmp))
                        {
                            if(tmp==endWord)return ret;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

4)为高尔夫比赛砍树

675. 为高尔夫比赛砍树

 

.1- 题目解析

        先找出砍树的顺序,然后按照砍树的顺序,一个一个用 BFS 求出最短路即可。

.2- 代码编写

class Solution {
    int m,n;
public:
    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>& p1,const pair<int,int>& p2)
        {
            return forest[p1.first][p1.second]<forest[p2.first][p2.second];
        });
        //按顺序砍树
        int bx=0,by=0;
        int ret=0;
        for(auto& [a,b]:trees)
        {
            int step=bfs(forest,bx,by,a,b);//找起始位置到终止位置的最短路径
            if(step==-1)return -1;
            ret+=step;
            bx=a,by=b;//继续遍历下一个位置
        }
        return ret;
    }
    bool vis[51][51];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey)
    {
        if(bx==ex && by==ey)return 0;//处理边界情况

        queue<pair<int,int>> q;
        memset(vis,0,sizeof(vis));//每次重新标识bfs
        q.push({bx,by});
        vis[bx][by]=true;
        int step=0;
        while(q.size())
        {
            step++;
            int sz=q.size();
            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 && forest[x][y] && !vis[x][y])
                    {
                        if(x==ex && y==ey)return step;
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }

};


原文地址:https://blog.csdn.net/waluolandao/article/details/142351485

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!