#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>#include <unordered_map>using namespace std;/*問題:Given two Words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:Only one letter can be changed at a time.Each transformed word must exist in the word list. Note that beginWord is not a transformed word.For example,Given:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log","cog"]As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.Note:Return 0 if there is no such transformation sequence.All words have the same length.All words contain only lowercase alphabetic characters.You may assume no duplicates in the word list.You may assume beginWord and endWord are non-empty and are not the same.分析：這是求最短字符串長度。廣度優先搜索用于求解最優問題。可以使用廣度優先搜索，設定每個字符串到初始字符串的距離。根據當前遍歷的字符串，找到其所有變位詞，遍歷變位詞，如果變位詞的距離已經被設置了則跳過（說明該單詞之前被訪問過，不可能在一個里面出現重復的變位詞），如果沒有訪問過，獲取當前單詞距離，設置變位詞的距離=當前單詞距離+1輸入:hit cog 6hot dot dog lot log coghit cog 5hot dot dog lot log輸出:50*/class Solution {public:	vector<string> getOneEditWords(string& word , unordered_map<string,int>& words , unordered_map<string , vector<string> >& wordToNextWords)	{		vector<string> nextWords;		if(word.empty())		{			return nextWords;		}		if(1 == wordToNextWords.count(word))		{			return wordToNextWords[word];		}		int len = word.length();		char temp;		for(int i = 0; i < len ; i++)		{			temp = word.at(i);			for(char ch = 'a' ; ch <= 'z' ; ch++)			{				word.at(i) = ch;				if(1 == words.count(word))				{					nextWords.push_back(word);				}				word.at(i) = temp;			}		}		wordToNextWords[word] = nextWords;		return nextWords;	}	int bfs(string beginWord, string endWord , vector<string>& wordList , 		unordered_map<string,int>& words , unordered_map<string , vector<string> >& wordToNextWords)	{		unordered_map<string ,int> strToDistance;		queue<string> queueWords;		queueWords.push(beginWord);		strToDistance[beginWord] = 0;		vector<string> nextWords;		string word;		string nextWord;		int curDistance = 0;		int size;		bool isFind = false;		while(!queueWords.empty())		{			word = queueWords.front();			queueWords.pop();			nextWords = getOneEditWords(word ,words , wordToNextWords);			if(nextWords.empty())			{				continue;			}			curDistance = strToDistance[word];			size = nextWords.size();			for(int i = 0 ; i < size ; i++)			{				nextWord = nextWords.at(i);				//如果沒有訪問過				if(strToDistance.find(nextWord) == strToDistance.end())				{					strToDistance[nextWord] = curDistance + 1;					queueWords.push(nextWord);					if(nextWord == endWord)					{						isFind = true;					}				}			}			if(isFind)			{				break;			}		}		if(isFind)		{			return (curDistance + 2);//curDistance需要加上從當前字符串到結尾字符串的距離1，以及多1個元素		}		else		{			return 0;		}	}    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {        if(beginWord.empty() || endWord.empty() || wordList.empty())		{			return 0;		}		unordered_map<string , int> words;		int size = wordList.size();		for(int i = 0; i < size ; i++)		{			words[ wordList.at(i) ] = 1;		}		unordered_map<string , vector<string> > wordToNextWords;		int result = bfs(beginWord, endWord , wordList , words , wordToNextWords);		return result;    }};void PRocess(){	 vector<string> nums;	 string value;	 int num;	 Solution solution;	 string beginWord;	 string endWord;	 vector<vector<string> > result;	 while(cin >> beginWord >> endWord >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 int distance = solution.ladderLength(beginWord , endWord , nums);		 cout << distance << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}