C++回溯算法廣度優(yōu)先搜索舉例分析
迷宮問題
假設有一個迷宮，里面有障礙物，迷宮用二維矩陣表示，標記為0的地方表示可以通過，標記為1的地方表示障礙物，不能通過?，F(xiàn)在給一個迷宮出口，讓你判斷是否可以從入口進來之后，走出迷宮，每次可以向任意方向走。
代碼實現(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;
//一個點的所有可能延伸的點
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;
//沒有走過且不是障礙物
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叉樹的層序遍歷
問題描述：
給定一個 N 叉樹，返回其節(jié)點值的層序遍歷。（即從左到右，逐層遍歷）。 樹的序列化輸入是用層序遍歷，每組子節(jié)點都由 null 值分隔（參見示例）。
代碼實現(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())
{
//獲取隊列中的元素個數(shù)
int sz = q.size();
vector<int> rowV;
while(sz--)
{
//保存當前元素在同一行
Node* node = q.front();
q.pop();
rowV.push_back(node->val);
//當前元素的孩子結(jié)點入隊
for(auto e : node->children)
{
q.push(e);
}
}
result.push_back(rowV);
}
return result;
}
};
腐爛的橘子
問題描述：
在給定的網(wǎng)格中，每個單元格可以有以下三個值之一：
值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。
返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能，返回 -1。
本題可以先找到所有的腐爛橘子入隊，用第一批帶出新一批腐爛的橘子。 每一批橘子都會在一分鐘之內(nèi)腐爛，所以此題可以轉(zhuǎn)化為求BFS執(zhí)行的大循環(huán)的次數(shù)。這里的step的更新需要有一個標記，只有新的腐爛的橘子加入，step才++ 最后BFS執(zhí)行完，說明所有可以被腐爛的都完成了，再去遍歷grid，如果還有值為1的，說明沒有辦法全部腐爛，返回-1，如果沒有，則返回step
代碼實現(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;
//把所有腐爛的橘子入隊
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;
}
};
單詞接龍
問題描述：
字典 wordList 中從單詞 beginWord 和 endWord 的 轉(zhuǎn)換序列 是一個按下述規(guī)格形成的序列：
序列中第一個單詞是 beginWord 。
序列中最后一個單詞是 endWord 。
每次轉(zhuǎn)換只能改變一個字母。
轉(zhuǎn)換過程中的中間單詞必須是字典 wordList 中的單詞。
給你兩個單詞 beginWord 和 endWord 和一個字典 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
解釋：一個最短轉(zhuǎn)換序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的長度 5。
1.通過BFS，首先用beginWord帶出轉(zhuǎn)換一個字符之后所有可能的結(jié)果
2.每一步都要把隊列中上一步添加的所有單詞轉(zhuǎn)換一遍，最短的轉(zhuǎn)換肯定在這些單詞中，所有這些詞的轉(zhuǎn)換只能算一次轉(zhuǎn)換，因為都是上一步轉(zhuǎn)換出來的，這里對于每個單詞的每個位置都可以用26個字母進行轉(zhuǎn)換，所以一個單詞一次轉(zhuǎn)換的可能有：單詞的長度*25
3.把轉(zhuǎn)換成功的新詞入隊，進行下一步的轉(zhuǎn)換
4.最后整個轉(zhuǎn)換的長度就和BFS執(zhí)行的次數(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;
//判斷新的單詞是否在詞典中，且沒被搜索過
if(dict.find(str1) != dict.end()
&& book.find(str1) == book.end()){
q.push(str1);
book.insert(str1);
}
}
}
}
++step;
}
return 0;
}
};
打開轉(zhuǎn)盤鎖
問題描述：
你有一個帶有四個圓形撥輪的轉(zhuǎn)盤鎖。每個撥輪都有10個數(shù)字： ‘0', ‘1', ‘2', ‘3', ‘4', ‘5', ‘6', ‘7', ‘8', ‘9' 。每個撥輪可以自由旋轉(zhuǎn)：例如把 ‘9' 變?yōu)?‘0'，‘0' 變?yōu)?‘9' 。每次旋轉(zhuǎn)都只能旋轉(zhuǎn)一個撥輪的一位數(shù)字。
鎖的初始數(shù)字為 ‘0000' ，一個代表四個撥輪的數(shù)字的字符串。
列表 deadends 包含了一組死亡數(shù)字，一旦撥輪的數(shù)字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉(zhuǎn)。
字符串 target 代表可以解鎖的數(shù)字，你需要給出解鎖需要的最小旋轉(zhuǎn)次數(shù)，如果無論如何不能解鎖，返回 -1 。
深度優(yōu)先不適合此題，遞歸深度太大，會導致棧溢出。
本題的密碼為4位密碼，每位密碼可以通過撥動一次進行改變，注意這里的數(shù)的回環(huán)以及撥動的方向撥動方向：向前，向后。
回環(huán)：如果當前是9，0時，向前，向后撥動需要變成最小最大，而不是簡單的自加自減。
0000一步旋轉(zhuǎn)后的結(jié)果有：
0001 0009 0010 0090 0100 0900 1000 9000
代碼實現(xiàn)：
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
unordered_set<string> deaddict(deadends.begin(), deadends.end());
//如果0000在死亡數(shù)字中，則永遠也到不了
if(deaddict.find("0000") != deaddict.end())
return -1;
queue<string> q;
q.push("0000");
//添加標記，已經(jīng)搜索過的字符不再搜索
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;
}
};
到此這篇關于C++回溯算法廣度優(yōu)先搜索舉例分析的文章就介紹到這了,更多相關C++ 回溯算法 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒)
這篇文章主要介紹了C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結(jié)構之迷宮問題，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
C語言深入講解之從函數(shù)棧幀角度理解return關鍵字
在C語言中,一般情況下函數(shù)的返回值是通過函數(shù)中的return語句來實現(xiàn)的,每調(diào)用一次return語句只能從函數(shù)中返回一個值,這篇文章主要給大家介紹了關于C語言從函數(shù)棧幀角度理解return關鍵字的相關資料,需要的朋友可以參考下2021-09-09
本文主要介紹tabWidget選擇夾組件與TreeWidget樹形選擇組件的常用方法及靈活運用,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-12-12
c++靜態(tài)局部變量和靜態(tài)函數(shù)示例
這篇文章主要介紹了c++靜態(tài)局部變量和靜態(tài)函數(shù)示例,需要的朋友可以參考下2014-04-04
這篇文章主要介紹了實現(xiàn)去除c語言注釋的小工具，說是C語言，但其實所有C語系的都可以，比如Java,需要的朋友可以參考下2014-02-02
C語言編程數(shù)據(jù)結(jié)構線性表之順序表和鏈表原理分析
本篇文章是C語言編程篇主要為大家介紹了C語言編程中的數(shù)據(jù)結(jié)構線性表，文中附含豐富的圖文示例代碼為大家詳解了線性表中的順序表和鏈表，有需要的朋友可以借鑒參考下2021-09-09
C++的“繼承”特性可以提高程序的可復用性。正因為“繼承”太有用、太容易用，才要防止亂用“繼承”2013-09-09
本文詳細介紹c++ map,mutimap刪除操作時的一些問題，提供了解決方法，需要的朋友可以參考下2012-11-11
VC使用TerminateProcess結(jié)束進程實例
這篇文章主要介紹了VC使用TerminateProcess結(jié)束進程的方法,實例演示了TerminateProcess結(jié)束進程的具體實現(xiàn)過程,在進行VC應用程序開發(fā)時非常具有實用價值,需要的朋友可以參考下2014-10-10