公司主營業(yè)務(wù):成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳,提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)建站是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化,感謝他們對我們的高要求,感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn),讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)建站推出化德免費做網(wǎng)站回饋大家。
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
bool connect(string &word1,string &word2)
{
int cnt = 0;
for(int i = 0; i < word1.length(); i++)
if(word1[i] != word2[i])
cnt++;
return cnt == 1;
}
void construct_graph(string &beginword,vector<string> &wordlist, map<string ,vector<string> > &graph)
{
wordlist.push_back(beginword);
for(int i = 0; i < wordlist.size(); i++)
graph[wordlist[i]] = 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 BFS_wordlist(string &beginword, string &endword, map<string, vector<string> > &graph)
{
queue<pair<string,int> > q;
set<string> visit;
q.push(make_pair(beginword,1));
visit.insert(beginword);
while(!q.empty())
{
string node = q.front().first;
int step = q.front().second;
q.pop();
if(node == endword)
{
return step;
}
vector<string> brothers = graph[node];
for(int i = 0; i < brothers.size(); i++)
{
if(visit.find(brothers[i]) == visit.end())
{
q.push(make_pair(brothers[i], step+1));
visit.insert(brothers[i]);
}
}
}
return 0;
}
int main()
{
string beginword,endword;
vector<string> wordlist;
map<string ,vector<string> > graph;
wordlist.push_back("hot");
wordlist.push_back("dot");
wordlist.push_back("dog");
wordlist.push_back("lot");
wordlist.push_back("log");
wordlist.push_back("cog");
cin>>beginword;
cin>>endword;
construct_graph(beginword,wordlist,graph);
cout<<BFS_wordlist(beginword,endword,graph);
return 0;
}
本文標題:javabfs實現(xiàn)單詞最少轉(zhuǎn)換次數(shù)
轉(zhuǎn)載源于:http://bm7419.com/article46/pceghg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供定制開發(fā)、App設(shè)計、做網(wǎng)站、建站公司、網(wǎng)站導(dǎo)航、軟件開發(fā)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)