具體步驟如下：

1. 初始化： 從起始點(diǎn)開(kāi)始，將其放入隊(duì)列中，并標(biāo)記為已訪問(wèn)。
2. BFS遍歷： 不斷從隊(duì)列中取出頂點(diǎn)，然后探索與該頂點(diǎn)相鄰且未被訪問(wèn)的頂點(diǎn)。對(duì)于每個(gè)相鄰頂點(diǎn)，將其標(biāo)記為已訪問(wèn)，并將其加入隊(duì)列。這樣，每一輪BFS都會(huì)探索到當(dāng)前距離起始點(diǎn)的步數(shù)更多的頂點(diǎn)。
3. 重復(fù)步驟2： 重復(fù)這個(gè)過(guò)程，直到找到目標(biāo)點(diǎn)或者隊(duì)列為空。
4. 路徑重建（可選）： 如果需要找到實(shí)際的路徑而不僅僅是路徑的長(zhǎng)度，通常在BFS的過(guò)程中維護(hù)一個(gè)記錄每個(gè)頂點(diǎn)是由哪個(gè)頂點(diǎn)發(fā)現(xiàn)的信息，然后通過(guò)回溯從目標(biāo)點(diǎn)追溯到起始點(diǎn)，重建路徑。

BFS的優(yōu)勢(shì)在于它保證首次到達(dá)目標(biāo)點(diǎn)的路徑就是最短路徑，因?yàn)樵?code>BFS的遍歷過(guò)程中，我們首次訪問(wèn)一個(gè)頂點(diǎn)時(shí)，它是離起始點(diǎn)最近的未訪問(wèn)頂點(diǎn)之一。

這種算法廣泛應(yīng)用于圖的最短路徑問(wèn)題，例如在無(wú)權(quán)圖中尋找最短路徑，或者在有權(quán)圖中，權(quán)值為1的情況下尋找最少步數(shù)的路徑。

01.迷宮中離入口最近的出口

題目鏈接：https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

給你一個(gè) m x n 的迷宮矩陣 maze （下標(biāo)從 0 開(kāi)始），矩陣中有空格子（用 '.' 表示）和墻（用 '+' 表示）。同時(shí)給你迷宮的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一開(kāi)始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移動(dòng)一個(gè)格子。你不能進(jìn)入墻所在的格子，你也不能離開(kāi)迷宮。你的目標(biāo)是找到離 entrance 最近 的出口。出口 的含義是 maze 邊界 上的 空格子。entrance 格子 不算 出口。

請(qǐng)你返回從 entrance 到最近出口的最短路徑的 步數(shù) ，如果不存在這樣的路徑，請(qǐng)你返回 -1 。

示例 1：

輸入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
輸出：1
解釋?zhuān)嚎偣灿?3 個(gè)出口，分別位于 (1,0)，(0,2) 和 (2,3) 。
一開(kāi)始，你在入口格子 (1,2) 處。
- 你可以往左移動(dòng) 2 步到達(dá) (1,0) 。
- 你可以往上移動(dòng) 1 步到達(dá) (0,2) 。
從入口處沒(méi)法到達(dá) (2,3) 。
所以，最近的出口是 (0,2) ，距離為 1 步。

示例 2：

輸入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
輸出：2
解釋?zhuān)好詫m中只有 1 個(gè)出口，在 (1,2) 處。
(1,0) 不算出口，因?yàn)樗侨肟诟褡印?初始時(shí)，你在入口與格子 (1,0) 處。
- 你可以往右移動(dòng) 2 步到達(dá) (1,2) 處。
所以，最近的出口為 (1,2) ，距離為 2 步。

示例 3：

輸入：maze = [[".","+"]], entrance = [0,0]
輸出：-1
解釋?zhuān)哼@個(gè)迷宮中沒(méi)有出口。

提示：

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 要么是 '.' ，要么是 '+' 。
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance 一定是空格子。

思路

這是屬于圖論中邊路權(quán)值為1的情況，利用層序遍歷來(lái)解決迷宮問(wèn)題是最經(jīng)典的做法。我們可以從起點(diǎn)開(kāi)始層序遍歷，并且在遍歷的過(guò)程中記錄當(dāng)前遍歷的層數(shù)。這樣就能在找到出口的時(shí)候，得到起點(diǎn)到出口的最短距離。

代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-829170.html

class Solution {
    const int dx[4]={0,0,1,-1};
    const int dy[4]={-1,1,0,0};

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        queue<pair<int,int>> q;
        int m=maze.size(),n=maze[0].size();
        int visit[m][n];
        memset(visit,0,sizeof visit);
        int step=0;

        q.push({entrance[0],entrance[1]});
        visit[entrance[0]][entrance[1]]=1;

        while(!q.empty()){
            step++;
            int sz=q.size();
            for(int i=0;i<sz;++i){
                auto [a,b]=q.front();
                q.pop();
                for(int k=0;k<4;++k){
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&maze[x][y]=='.'&&!visit[x][y]){
                        if(x==0||x==m-1||y==0||y==n-1) return step;
                        q.push({x,y});
                        visit[x][y]=1;
                    }
                }
            }
        }
        return -1;
    }
};

1. 定義了常量數(shù)組 dx 和 dy 表示上下左右四個(gè)方向。
2. 使用 BFS 進(jìn)行迷宮遍歷。
3. 使用隊(duì)列 q 存儲(chǔ)當(dāng)前需要遍歷的點(diǎn)，使用數(shù)組 visit 記錄是否訪問(wèn)過(guò)。
4. 將入口點(diǎn)入隊(duì)，并標(biāo)記為已訪問(wèn)。
5. 在每一步中，從隊(duì)列中取出當(dāng)前層次的所有點(diǎn)，并嘗試在四個(gè)方向上擴(kuò)展。
6. 如果擴(kuò)展到邊界，說(shuō)明找到了最近的出口，返回步數(shù)。
7. 如果隊(duì)列為空仍未找到，說(shuō)明無(wú)法找到出口，返回 -1。

02.最小基因變化

題目鏈接：https://leetcode.cn/problems/minimum-genetic-mutation/

基因序列可以表示為一條由 8 個(gè)字符組成的字符串，其中每個(gè)字符都是 'A'、'C'、'G' 和 'T' 之一。

假設(shè)我們需要調(diào)查從基因序列 start 變?yōu)?end 所發(fā)生的基因變化。一次基因變化就意味著這個(gè)基因序列中的一個(gè)字符發(fā)生了變化。

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

另有一個(gè)基因庫(kù) bank 記錄了所有有效的基因變化，只有基因庫(kù)中的基因才是有效的基因序列。（變化后的基因必須位于基因庫(kù) bank 中）

給你兩個(gè)基因序列 start 和 end ，以及一個(gè)基因庫(kù) bank ，請(qǐng)你找出并返回能夠使 start 變化為 end 所需的最少變化次數(shù)。如果無(wú)法完成此基因變化，返回 -1 。

注意：起始基因序列 start 默認(rèn)是有效的，但是它并不一定會(huì)出現(xiàn)在基因庫(kù)中。

示例 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 

提示：

• start.length == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 僅由字符 ['A', 'C', 'G', 'T'] 組成

思路

其實(shí)這也可以直接轉(zhuǎn)化成邊路權(quán)值為1的圖論問(wèn)題。具體思路是：

1. 使用哈希集合 hash 存儲(chǔ)基因庫(kù)，便于快速查詢某個(gè)基因是否合法。
2. 使用廣度優(yōu)先搜索（BFS），從起始基因開(kāi)始，不斷變異基因，直到找到目標(biāo)基因?yàn)橹埂?/li>
3. 在每一步中，對(duì)當(dāng)前基因的每個(gè)位置嘗試變異成可能的字符，如果變異后的基因是合法的且未被訪問(wèn)過(guò)，就加入隊(duì)列中，并標(biāo)記為已訪問(wèn)。
4. 如果隊(duì)列為空仍未找到目標(biāo)基因，返回-1，表示無(wú)法變異到目標(biāo)基因。
5. 如果找到目標(biāo)基因，返回步數(shù)

代碼

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis;  // 用于記錄已經(jīng)訪問(wèn)過(guò)的基因序列
        unordered_set<string> hash(bank.begin(), bank.end());  // 將基因庫(kù)放入哈希集合中，方便查詢是否是合法基因

        if (startGene == endGene) return 0;  // 如果起始基因和目標(biāo)基因相同，不需要變異，返回步數(shù)為0
        if (!hash.count(endGene)) return -1;  // 如果目標(biāo)基因不在基因庫(kù)中，無(wú)法變異到目標(biāo)基因，返回-1

        string change = "ACGT";  // 可能的基因變異字符
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);

        int ret = 0;
        while (!q.empty()) {
            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];  // 嘗試將當(dāng)前位置的基因變異為可能的字符
                        if (hash.count(tmp) && !vis.count(tmp)) {  // 如果變異后的基因是合法的且未被訪問(wèn)過(guò)
                            if (tmp == endGene) return ret;  // 如果變異后的基因與目標(biāo)基因相同，返回步數(shù)
                            q.push(tmp);
                            vis.insert(tmp);  // 標(biāo)記為已訪問(wèn)
                        }
                    }
                }
            }
        }
        return -1;  // 如果隊(duì)列為空仍未找到目標(biāo)基因，說(shuō)明無(wú)法變異到目標(biāo)基因，返回-1
    }
};

03.單詞接龍

題目鏈接：https://leetcode.cn/problems/word-ladder/

字典 wordList 中從單詞 beginWord 和 endWord 的 轉(zhuǎn)換序列 是一個(gè)按下述規(guī)格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一對(duì)相鄰的單詞只差一個(gè)字母。
• 對(duì)于 1 <= i <= k 時(shí)，每個(gè) si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

給你兩個(gè)單詞 beginWord 和 endWord 和一個(gè)字典 wordList ，返回 從 beginWord 到 endWord 的 最短轉(zhuǎn)換序列 中的 單詞數(shù)目 。如果不存在這樣的轉(zhuǎn)換序列，返回 0 。

示例 1：

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
輸出：5
解釋?zhuān)阂粋€(gè)最短轉(zhuǎn)換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的長(zhǎng)度 5。

示例 2：

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
輸出：0
解釋?zhuān)篹ndWord "cog" 不在字典中，所以無(wú)法進(jìn)行轉(zhuǎn)換。 

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小寫(xiě)英文字母組成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

思路

其實(shí)這道困難題和上面的題思路基本一致，只不過(guò)變化范圍擴(kuò)大到了26個(gè)小寫(xiě)字母，還有返回值的計(jì)算。

1. 使用哈希集合 hash 存儲(chǔ)單詞列表，便于快速查詢某個(gè)單詞是否合法。
2. 使用廣度優(yōu)先搜索（BFS），從起始單詞開(kāi)始，不斷替換單詞的每個(gè)位置的字符，直到找到目標(biāo)單詞為止。
3. 在每一步中，對(duì)當(dāng)前單詞的每個(gè)位置嘗試替換成可能的字符，如果替換后的單詞是合法的且未被訪問(wèn)過(guò)，就加入隊(duì)列中，并標(biāo)記為已訪問(wèn)。
4. 如果隊(duì)列為空仍未找到目標(biāo)單詞，返回0，表示無(wú)法接龍到目標(biāo)單詞。
5. 如果找到目標(biāo)單詞，返回步數(shù)。

代碼

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vis;  // 用于記錄已經(jīng)訪問(wèn)過(guò)的單詞
        unordered_set<string> hash(wordList.begin(), wordList.end());  // 將單詞列表放入哈希集合中，方便查詢是否是合法單詞

        if (beginWord == endWord) return 1;  // 如果起始單詞和目標(biāo)單詞相同，不需要接龍，返回步數(shù)為1
        if (!hash.count(endWord)) return 0;  // 如果目標(biāo)單詞不在單詞列表中，無(wú)法接龍到目標(biāo)單詞，返回0

        int ret = 1;
        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        while (!q.empty()) {
            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 c = 'a'; c <= 'z'; ++c) {
                        tmp[i] = c;  // 嘗試將當(dāng)前位置的字符替換為可能的字符
                        if (hash.count(tmp) && !vis.count(tmp)) {  // 如果替換后的單詞是合法的且未被訪問(wèn)過(guò)
                            if (tmp == endWord) return ret;  // 如果替換后的單詞與目標(biāo)單詞相同，返回步數(shù)
                            q.push(tmp);
                            vis.insert(tmp);  // 標(biāo)記為已訪問(wèn)
                        }
                    }
                }
            }
        }
        return 0;  // 如果隊(duì)列為空仍未找到目標(biāo)單詞，說(shuō)明無(wú)法接龍到目標(biāo)單詞，返回0
    }
};

04.為高爾夫比賽砍樹(shù)

題目鏈接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/

你被請(qǐng)來(lái)給一個(gè)要舉辦高爾夫比賽的樹(shù)林砍樹(shù)。樹(shù)林由一個(gè) m x n 的矩陣表示， 在這個(gè)矩陣中：

• 0 表示障礙，無(wú)法觸碰
• 1 表示地面，可以行走
• 比 1 大的數(shù) 表示有樹(shù)的單元格，可以行走，數(shù)值表示樹(shù)的高度

每一步，你都可以向上、下、左、右四個(gè)方向之一移動(dòng)一個(gè)單位，如果你站的地方有一棵樹(shù)，那么你可以決定是否要砍倒它。

你需要按照樹(shù)的高度從低向高砍掉所有的樹(shù)，每砍過(guò)一顆樹(shù)，該單元格的值變?yōu)?1（即變?yōu)榈孛妫?/p>

你將從 (0, 0) 點(diǎn)開(kāi)始工作，返回你砍完所有樹(shù)需要走的最小步數(shù)。 如果你無(wú)法砍完所有的樹(shù)，返回 -1 。

可以保證的是，沒(méi)有兩棵樹(shù)的高度是相同的，并且你至少需要砍倒一棵樹(shù)。

示例 1：

輸入：forest = [[1,2,3],[0,0,4],[7,6,5]]
輸出：6
解釋?zhuān)貉刂厦娴穆窂?，你可以?6 步，按從最矮到最高的順序砍掉這些樹(shù)。

示例 2：

輸入：forest = [[1,2,3],[0,0,0],[7,6,5]]
輸出：-1
解釋?zhuān)河捎谥虚g一行被障礙阻塞，無(wú)法訪問(wèn)最下面一行中的樹(shù)。

示例 3：

輸入：forest = [[2,3,4],[0,0,5],[8,7,6]]
輸出：6
解釋?zhuān)嚎梢园磁c示例 1 相同的路徑來(lái)砍掉所有的樹(shù)。
(0,0) 位置的樹(shù)，可以直接砍去，不用算步數(shù)。

提示：

• m == forest.length
• n == forest[i].length
• 1 <= m, n <= 50
• 0 <= forest[i][j] <= 109

思路

這里和之前的題不一樣的地方是，我們每次都要找到最矮的樹(shù)依次砍完所有的數(shù)，所以我們要針對(duì)從小到大每顆數(shù)的相對(duì)位置進(jìn)行BFS遍歷計(jì)算步數(shù)。

1. 遍歷整個(gè)矩形森林，將樹(shù)木的位置加入 trees 數(shù)組中。
2. 根據(jù)樹(shù)木的高度進(jìn)行排序。
3. 遍歷排好序的樹(shù)木數(shù)組，使用廣度優(yōu)先搜索（BFS）計(jì)算從當(dāng)前位置 (bx, by) 到目標(biāo)位置 (a, b) 的步數(shù)。
4. 如果無(wú)法到達(dá)目標(biāo)位置，返回 -1。
5. 累加步數(shù)，并更新起始位置 (bx, by)。
6. 最終返回累加的步數(shù)作為結(jié)果。

代碼

class Solution {
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {-1, 1, 0, 0};
    int m, n;
    int vis[51][51];

    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey) return 0;  // 如果起始位置和目標(biāo)位置相同，步數(shù)為0

        queue<pair<int, int>> q;
        memset(vis, 0, sizeof vis);
        q.push({bx, by});
        vis[bx][by] = 1;

        int step = 0;
        while (!q.empty()) {
            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;  // 如果到達(dá)目標(biāo)位置，返回步數(shù)
                        q.push({x, y});
                        vis[x][y] = 1;  // 標(biāo)記為已訪問(wèn)
                    }
                }
            }
        }
        return -1;  // 如果未能到達(dá)目標(biāo)位置，返回-1表示無(wú)法到達(dá)
    }

public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size(), n = forest[0].size();
        vector<pair<int, int>> trees;
        
        // 遍歷整個(gè)矩形森林，將樹(shù)木的位置加入trees數(shù)組中
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest[i][j] > 1) trees.push_back({i, j});
            }
        }

        // 根據(jù)樹(shù)木的高度進(jìn)行排序
        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;  // 起始位置為(0, 0)
        int ret = 0;

        // 遍歷排好序的樹(shù)木數(shù)組
        for (auto& [a, b] : trees) {
            // 使用BFS計(jì)算從當(dāng)前位置到目標(biāo)位置的步數(shù)
            int step = bfs(forest, bx, by, a, b);
            if (step == -1) return -1;  // 如果無(wú)法到達(dá)目標(biāo)位置，返回-1
            ret += step;  // 累加步數(shù)
            bx = a, by = b;  // 更新起始位置
        }
        return ret;
    }
};

到了這里，關(guān)于算法沉淀——BFS 解決最短路問(wèn)題（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！