首页 > 其他 > 详细

BFS之单词最少转换次数

时间:2020-02-18 11:09:52      阅读:57      评论:0      收藏:0      [点我收藏+]
#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; }

BFS之单词最少转换次数

原文:https://blog.51cto.com/14472348/2471592

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!