#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;}