C++回溯算法廣度優(yōu)先搜索舉例分析

更新時(shí)間：2022年03月24日 16:13:17 作者：ymz123_

回溯在迷宮搜索中使用很常見(jiàn)，就是這條路走不通，然后返回前一個(gè)路口，繼續(xù)下一條路。回溯算法說(shuō)白了就是窮舉法，下面讓我們一起來(lái)看看吧

迷宮問(wèn)題

假設(shè)有一個(gè)迷宮，里面有障礙物，迷宮用二維矩陣表示，標(biāo)記為0的地方表示可以通過(guò)，標(biāo)記為1的地方表示障礙物，不能通過(guò)?，F(xiàn)在給一個(gè)迷宮出口，讓你判斷是否可以從入口進(jìn)來(lái)之后，走出迷宮，每次可以向任意方向走。

代碼實(shí)現(xiàn)：

namespace BFS {
	struct pair {
		int _x;
		int _y;

		pair(int x, int y)
			:_x(x)
			, _y(y)
		{}
	};

	bool mapBFS(vector<vector<int>> mat, int sx, int sy, int ex, int ey)
	{
		int row = mat.size();
		int col = mat[0].size();

		queue<pair> q;
		q.push(pair(sx, sy));
		vector<vector<int>> book(row, vector<int>(col, 0));
		book[sx][sy] = 1;

		int nextP[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

		while (!q.empty())
		{
			pair curPos = q.front();
			q.pop();
			if (curPos._x == ex && curPos._y == ey)
				return true;
			//一個(gè)點(diǎn)的所有可能延伸的點(diǎn)
			for (int i = 0; i < 4; i++)
			{
				int curX = curPos._x + nextP[i][0];
				int curY = curPos._y + nextP[i][1];

				if (curX < 0 || curX >= row || curY < 0 || curY >= col)
					continue;
				//沒(méi)有走過(guò)且不是障礙物
				if (mat[curX][curY] == 0 && book[curX][curY] == 0)
				{
					book[curX][curY] = 1;
					//保存新的位置
					q.push(pair(curX, curY));
				}
			}
		}

		return false;
	}
}

int main()
{
	vector<vector<int>> mat{ {0, 0, 1, 0},
							 {1, 0, 0, 1},
							 {0, 0, 0, 0},
							 {1, 1, 0, 0} };
	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;
	cout << BFS::mapBFS(mat, sx, sy, ex, ey);

	return 0;
}

N叉樹(shù)的層序遍歷

問(wèn)題描述：

給定一個(gè) N 叉樹(shù)，返回其節(jié)點(diǎn)值的層序遍歷。（即從左到右，逐層遍歷）。樹(shù)的序列化輸入是用層序遍歷，每組子節(jié)點(diǎn)都由 null 值分隔（參見(jiàn)示例）。

代碼實(shí)現(xiàn)：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(!root)
            return result;
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
            //獲取隊(duì)列中的元素個(gè)數(shù)
            int sz = q.size();
            vector<int> rowV;
            while(sz--)
            {
                //保存當(dāng)前元素在同一行
                Node* node = q.front();
                q.pop();
                rowV.push_back(node->val);
                //當(dāng)前元素的孩子結(jié)點(diǎn)入隊(duì)
                for(auto e : node->children)
                {
                    q.push(e);
                }
            }
            result.push_back(rowV);
        }

        return result;
    }
};

腐爛的橘子

問(wèn)題描述：

在給定的網(wǎng)格中，每個(gè)單元格可以有以下三個(gè)值之一：

值 0 代表空單元格；

值 1 代表新鮮橘子；

值 2 代表腐爛的橘子。

每分鐘，任何與腐爛的橘子（在 4 個(gè)正方向上）相鄰的新鮮橘子都會(huì)腐爛。

返回直到單元格中沒(méi)有新鮮橘子為止所必須經(jīng)過(guò)的最小分鐘數(shù)。如果不可能，返回 -1。

本題可以先找到所有的腐爛橘子入隊(duì)，用第一批帶出新一批腐爛的橘子。每一批橘子都會(huì)在一分鐘之內(nèi)腐爛，所以此題可以轉(zhuǎn)化為求BFS執(zhí)行的大循環(huán)的次數(shù)。這里的step的更新需要有一個(gè)標(biāo)記，只有新的腐爛的橘子加入，step才++ 最后BFS執(zhí)行完，說(shuō)明所有可以被腐爛的都完成了，再去遍歷grid，如果還有值為1的，說(shuō)明沒(méi)有辦法全部腐爛，返回-1，如果沒(méi)有，則返回step

代碼實(shí)現(xiàn)：

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int step = 0;
        int row = grid.size();
        int col = grid[0].size();
        queue<pair<int, int>> q;
        //把所有腐爛的橘子入隊(duì)
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 2)
                    q.push(make_pair(i, j));
            }
        }

        static int nextP[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0 ,1}};
        while(!q.empty()){
            int sz = q.size();
            bool flag = false;
            while(sz--){
                pair curPos = q.front();
                q.pop();
                for(int i = 0; i < 4; i++){
                    int curX = curPos.first + nextP[i][0];
                    int curY = curPos.second + nextP[i][1];
                    if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                        continue;
                    if(grid[curX][curY] == 1){
                        flag = true;
                        grid[curX][curY] = 2;
                        q.push(make_pair(curX, curY));
                    }
                }
            }
            if(flag)
                ++step;
        }

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1)
                    return -1;
            }
        }

        return step;
    }
};

單詞接龍

問(wèn)題描述：

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

序列中第一個(gè)單詞是 beginWord 。

序列中最后一個(gè)單詞是 endWord 。

每次轉(zhuǎn)換只能改變一個(gè)字母。

轉(zhuǎn)換過(guò)程中的中間單詞必須是字典 wordList 中的單詞。

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

示例 1：

輸入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“l(fā)ot”,“l(fā)og”,“cog”]

輸出：5

解釋：一個(gè)最短轉(zhuǎn)換序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的長(zhǎng)度 5。

1.通過(guò)BFS，首先用beginWord帶出轉(zhuǎn)換一個(gè)字符之后所有可能的結(jié)果

2.每一步都要把隊(duì)列中上一步添加的所有單詞轉(zhuǎn)換一遍，最短的轉(zhuǎn)換肯定在這些單詞中，所有這些詞的轉(zhuǎn)換只能算一次轉(zhuǎn)換，因?yàn)槎际巧弦徊睫D(zhuǎn)換出來(lái)的，這里對(duì)于每個(gè)單詞的每個(gè)位置都可以用26個(gè)字母進(jìn)行轉(zhuǎn)換，所以一個(gè)單詞一次轉(zhuǎn)換的可能有：?jiǎn)卧~的長(zhǎng)度*25

3.把轉(zhuǎn)換成功的新詞入隊(duì)，進(jìn)行下一步的轉(zhuǎn)換

4.最后整個(gè)轉(zhuǎn)換的長(zhǎng)度就和BFS執(zhí)行的次數(shù)相同

需要判斷單詞有沒(méi)有被搜索過(guò)，是一個(gè)查詢的過(guò)程，可以用哈希表

代碼實(shí)現(xiàn)：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int step = 1;
        unordered_set<string> book;
        unordered_set<string> dict;
        book.insert(beginWord);
        for(string& ch : wordList)
            dict.insert(ch);
        queue<string> q;
        q.push(beginWord);

        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == endWord)
                    return step;
                for(int i = 0; i < curStr.size(); i++){
                    string str1 = curStr;
                    for(char ch = 'a'; ch <= 'z'; ++ch){
                        str1[i] = ch;
                        //判斷新的單詞是否在詞典中，且沒(méi)被搜索過(guò)
                        if(dict.find(str1) != dict.end()
                        && book.find(str1) == book.end()){
                            q.push(str1);
                            book.insert(str1);
                        }
                    }
                }
            }
            ++step;
        }
        
        return 0;
    }
};

打開(kāi)轉(zhuǎn)盤(pán)鎖

問(wèn)題描述：

你有一個(gè)帶有四個(gè)圓形撥輪的轉(zhuǎn)盤(pán)鎖。每個(gè)撥輪都有10個(gè)數(shù)字： ‘0', ‘1', ‘2', ‘3', ‘4', ‘5', ‘6', ‘7', ‘8', ‘9' 。每個(gè)撥輪可以自由旋轉(zhuǎn)：例如把 ‘9' 變?yōu)?‘0'，‘0' 變?yōu)?‘9' 。每次旋轉(zhuǎn)都只能旋轉(zhuǎn)一個(gè)撥輪的一位數(shù)字。

鎖的初始數(shù)字為 ‘0000' ，一個(gè)代表四個(gè)撥輪的數(shù)字的字符串。

列表 deadends 包含了一組死亡數(shù)字，一旦撥輪的數(shù)字和列表里的任何一個(gè)元素相同，這個(gè)鎖將會(huì)被永久鎖定，無(wú)法再被旋轉(zhuǎn)。

字符串 target 代表可以解鎖的數(shù)字，你需要給出解鎖需要的最小旋轉(zhuǎn)次數(shù)，如果無(wú)論如何不能解鎖，返回 -1 。

深度優(yōu)先不適合此題，遞歸深度太大，會(huì)導(dǎo)致棧溢出。

本題的密碼為4位密碼，每位密碼可以通過(guò)撥動(dòng)一次進(jìn)行改變，注意這里的數(shù)的回環(huán)以及撥動(dòng)的方向撥動(dòng)方向：向前，向后。

回環(huán)：如果當(dāng)前是9，0時(shí)，向前，向后撥動(dòng)需要變成最小最大，而不是簡(jiǎn)單的自加自減。

0000一步旋轉(zhuǎn)后的結(jié)果有：

0001 0009 0010 0090 0100 0900 1000 9000

代碼實(shí)現(xiàn)：

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deaddict(deadends.begin(), deadends.end());
        //如果0000在死亡數(shù)字中，則永遠(yuǎn)也到不了
        if(deaddict.find("0000") != deaddict.end())
            return -1;
        queue<string> q;
        q.push("0000");
        //添加標(biāo)記，已經(jīng)搜索過(guò)的字符不再搜索
        unordered_set<string> book;
        book.insert("0000");
        int step = 0;
        while(!q.empty()){
            int size = q.size();
            while(size--){
                string curStr = q.front();
                q.pop();
                if(curStr == target)
                    return step;
                for(int i = 0; i < 4; i++){
                    string s1 = curStr;
                    string s2 = curStr;
                    //向前或向后旋轉(zhuǎn)
                    s1[i] = s1[i] =='0' ? '9' : --s1[i];
                    s2[i] = s2[i] =='9' ? '0' : ++s2[i];
                    if(deaddict.find(s1) == deaddict.end()
                    && book.find(s1) == book.end()){
                        q.push(s1);
                        book.insert(s1);
                    }
                    if(deaddict.find(s2) == deaddict.end()
                    && book.find(s2) == book.end()){
                        q.push(s2);
                        book.insert(s2);
                    }
                }
            }
            ++step;
        }

        return -1;
    }
};

到此這篇關(guān)于C++回溯算法廣度優(yōu)先搜索舉例分析的文章就介紹到這了,更多相關(guān)C++ 回溯算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: