問題描述以及解決過程如下導(dǎo)圖

廣搜實現(xiàn)如下

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>using namespace std;/*判斷兩個單詞是否有連接狀態(tài)*/
bool connect(string &word1, string &word2) {if (word1.length() == 0 || word2.length() == 0) {return false;}int cnt = 0;for (int i = 0; i < word1.length(); ++i) {if (word1[i] != word2[i]) {cnt ++;}}if (cnt == 1) {return true;}return false;
}/*構(gòu)建圖*/
void get_graph(string &begin_word, std::vector<string> &wordList,std::map<string, std::vector<string> > &graph) {wordList.push_back(begin_word);for (int i = 0;i < wordList.size(); ++i ) {graph[wordList[i]]= std::vector<string> ();}for (int i = 0;i < wordList.size(); ++i) {for (int j = i + 1; j < wordList.size(); ++j) {if (connect(wordList[i], wordList[j])) {graph[wordList[i]].push_back(wordList[j]);graph[wordList[j]].push_back(wordList[i]);}}}
}/*廣搜獲取最短長度*/
int get_length(string &begin_word, string &end_word,std::map<string, std::vector<string> > graph) {queue<pair<string,int>> Q;set<string> visit;Q.push(make_pair(begin_word,1));visit.insert(begin_word);while(!Q.empty()) {/* code */string node = Q.front().first;int step = Q.front().second;Q.pop();if (node == end_word) {return step;}std::vector<string> node_v = graph[node];for (int i = 0;i < node_v.size(); ++i) {if (visit.find(node_v[i]) == visit.end()) {Q.push(make_pair(node_v[i], step + 1));visit.insert(node_v[i]);}}	}return 0;
}int get_result(string &begin_word, string &end_word, std::vector<string> &wordList) {std::map<string, std::vector<string> > graph;get_graph(begin_word,wordList,graph);return get_length(begin_word,end_word,graph);
}int main(int argc, char const *argv[])
{string begin_word = "hit";string end_word = "cog";std::vector<string> word_list;for (int i = 0;i < 6; ++i) {string tmp;cin >> tmp;word_list.push_back(tmp);}cout << get_result(begin_word, end_word, word_list);return 0;
}

輸出如下:

#輸入
hot 
dot
dog
log
lot
cog#輸出
5

總結(jié)

以上是生活随笔為你收集整理的搜索：广搜 词语阶梯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。