C++优选算法十六 BFS解决最短路问题

1.BFS解决最短路问题的优势与局限

BFS是一种有效的解决最短路问题的算法，特别适用于无权图或边权相等的图。

优势：

• BFS能够逐层遍历图中的所有节点，直到找到目标节点或遍历完所有可达节点。
• 对于无权图（即边权为1的图）或边权相等的图，BFS能够找到从起点到目标节点的最短路径。

局限：

• BFS需要存储所有待访问的节点，因此空间复杂度较高。
• 对于边权不相等的图，BFS无法找到最短路径，因为BFS总是先访问先加入的节点，而不考虑边的权重。

接下来的题目都是基础的边权为1的最短路问题。

从起点开始来一次BFS。

循环pop，再将相连的节点push进来。
最短路：扩展的层数！

2.例题

2.1迷宫中离入口最近的出口

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

示例 1：

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。

示例 2：

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。

示例 3：

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

解法(bfs 求最短路)
算法思路:利用层序遍历来解决迷宫问题，是最经典的做法。
我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离。 

class Solution {
    typedef pair<int,int> PII;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        queue<PII> qe;
        int i=entrance[0];
        int j=entrance[1];
        qe.push({i,j});
        int n=maze.size();
        int m=maze[0].size();
        vector<vector<bool>> vv(n,vector<bool>(m,false));

        int count=0;//记录层数/步数
        int d=qe.size();
        while(qe.size())
        { 
            count++;
            while(d--)
            {
                auto [a,b]=qe.front();
                qe.pop();
                vv[a][b]=true;
                for(int k=0;k<4;k++)
                {
                    int x=a+dx[k];
                    int y=b+dy[k];
                    if(x>=0&&x<n&&y>=0&&y<m&&vv[x][y]==false&&maze[x][y]=='.')
                    {
                        qe.push({x,y});
                        vv[x][y]=true;
                        if(x==0||x==n-1||y==0||y==m-1)//判断是否找到出口
                            return count;
                    }
                }
            }
            d=qe.size();
        }
        return -1;
    }
};

2.2 最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

解法:
算法思路:        
如果将「每次字符串的变换」抽象成图中的「两个顶点和一条边」的话，问题就变成了「边权为 1的最短路问题」。
因此，从起始的字符串开始，来一次 bfs 即可。 

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) 
    {
        if(bank.size()==0)
            return -1;
        queue<string> qe;
        qe.push(startGene);

        unordered_map<string,int> vis_hash;//标记已经搜索过的状态
        vis_hash[startGene]++;
        unordered_map<string,int> bk_hash;//存储基因库里面的字符串
        for(auto str:bank)
        {
            bk_hash[str]++;
        }

        int n=4;
        vector<char> ch={'A','C','G','T'};
        int m=startGene.size();
        int count=0;
        while(qe.size())
        {
            count++;
            int d=qe.size();
            while(d--)
            {
                string ctr=qe.front();
                string str=ctr;//复制一份
                qe.pop();
                for(int i=0;i<m;i++)
                {
                    for(int j=0;j<n;j++)
                    {
                        str[i]=ch[j];//每个节点变化，再去基因库中查找
                        if(bk_hash.count(str)&&!vis_hash.count(str))
                        {
                            if(str==endGene)
                                return count;
                            qe.push(str);
                            vis_hash[str]++;
                        }
                    }
                    str=ctr;//恢复
                }
            }
        }
        return -1;
    }
};

2.3单词接龙

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

 

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

解法：与上题思路一致。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        int n = beginWord.size();
        queue<string> qe;
        unordered_map<string, int> list_hash;//保存字典中的单词
        for (auto str : wordList)
        {
            list_hash[str]++;
        }

        string sr = "qwertyuioplkjhgfdsazxcvbnm";
        unordered_map<string, int> word_hash;
        qe.push(beginWord);

        int count = 0;
        while (qe.size())
        {
            count++;
            int d = qe.size();
            while (d--)
            {
                string str = qe.front();
                qe.pop();
                for (int i = 0; i < n; i++)
                {
                    string st = str;
                    for (int j = 0; j < 26; j++)
                    {
                        st[i] = sr[j];
                        if (list_hash.count(st) && !word_hash.count(st))
                        {
                            if (st == endWord)
                                return count + 1;
                            qe.push(st);
                            word_hash[st]++;
                        }
                    }
                }
            }
        }
        return 0;
    }
};

 2.4为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

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

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

解法:
算法思路:
        a.先找出砍树的顺序;
        b.然后按照砍树的顺序，一个一个的用 bfs 求出最短路即可。

class Solution {
public:
    int m,n;
    int cutOffTree(vector<vector<int>>& f) 
    {
        m=f.size();
        n=f[0].size();

        //1.找出砍树的顺序
        vector<pair<int,int>> trees;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(f[i][j]>1)
                    trees.push_back({i,j});
            }
        }

        sort(trees.begin(),trees.end(),[&](const pair<int,int>&p1,const pair<int,int>&p2)
        {
            return f[p1.first][p1.second]<f[p2.first][p2.second];
        });

        //2.按照顺序砍树
        int bx=0;
        int by=0;
        int ret=0;
        for(auto &[a,b]:trees)
        {
            int step=bfs(f,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>>&f,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));
        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];
                    int y=b+dy[i];
                    if(x>=0&&x<m&&y>=0&&y<n&&f[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/m0_74826386/article/details/144140534

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