#include #include #include #include #include #include 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 &wordlist, map > &graph) { wordlist.push_back(beginword); for(int i = 0; i < wordlist.size(); i++) graph[wordlist[i]] = vector(); 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 > &graph) { queue > q; set 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 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 wordlist; map > 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<
