UVa 429 Word Transformation

题目描述题目要求计算从起始单词变换到目标单词的最短步数。每次变换只能改变单词中的一个字母且变换后的单词必须存在于给定的字典中。所有单词长度相同。对于每对起始词和目标词输出最短变换步数。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例包含两个部分字典部分若干行每行一个单词小写字母长度不超过101010以一行单独的*结束。字典中最多200200200个单词。查询部分若干行每行两个单词起始词和目标词用一个空格分隔。每对单词均保证存在变换路径。输入以文件结束符EOF\texttt{EOF}EOF终止。两个连续的测试用例之间由一个空行分隔。输出格式对于每个查询输出一行包含起始词、目标词和最短步数之间用单个空格分隔。两个连续的测试用例输出之间由一个空行分隔。样例输入1 dip lip mad map maple may pad pip pod pop sap sip slice slick spice stick stock * spice stock may pod输出spice stock 4 may pod 3题目分析本题的核心是在单词图中求两点之间的最短路径。每个单词是一个节点若两个单词长度相同且仅有一个字母不同则它们之间有一条无向边。图的构建由于字典中最多200200200个单词可以枚举所有单词对检查它们是否长度相同且恰好有一个字符不同。若是则在两者之间建立一条边。构建图的时间复杂度为O(n2×L)O(n^2 \times L)O(n2×L)n≤200n \le 200n≤200L≤10L \le 10L≤10完全可接受。最短路径计算对于每个查询起始词sss和目标词ttt使用广度优先搜索BFS\texttt{BFS}BFS计算从sss到ttt的最短路径长度。由于所有边权均为111BFS\texttt{BFS}BFS可以保证找到最短路径。实现细节字典中单词可能重复需去重。需要为每个单词分配一个整数索引以便在图中使用。BFS\texttt{BFS}BFS时记录每个节点的距离初始距离dist[s]0\textit{dist}[s] 0dist[s]0队列中存放节点编号。由于每组查询独立可以在每次查询时重新运行BFS\texttt{BFS}BFS。复杂度分析图构建O(n2×L)O(n^2 \times L)O(n2×L)n≤200n \le 200n≤200L≤10L \le 10L≤10约4×1054 \times 10^54×105次操作。每次查询BFS\texttt{BFS}BFSO(nm)O(n m)O(nm)其中mmm为边数最多O(n2)O(n^2)O(n2)。总复杂度可接受。代码实现// Word Transformation// UVa ID: 429// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_STEPS1000000;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);getline(cin,line);for(intm1;mcases;m){if(m1)coutendl;setstringexisted;mapstring,intwords;vectorstringdictionary;intn0;while(getline(cin,line),line!*){if(existed.find(line)existed.end()){existed.insert(line);dictionary.push_back(line);words[line]n;}}vectorvectorintedges(n,vectorint());for(inti0;in;i)for(intji1;jn;j){if(dictionary[i].length()!dictionary[j].length())continue;intdifference0;for(intk0;kdictionary[i].length();k)if(dictionary[i][k]!dictionary[j][k])difference;if(difference1){edges[i].push_back(j);edges[j].push_back(i);}}while(getline(cin,line),line.length()0){istringstreamiss(line);string first,second;issfirstsecond;intstartwords[first],endwords[second];vectorboolvisited(n);vectorintdistances(n);fill(distances.begin(),distances.end(),MAX_STEPS);fill(visited.begin(),visited.end(),false);distances[start]0;intcurrentstart;while(visited[current]false){visited[current]true;for(inti0;iedges[current].size();i){intnextedges[current][i];if(visited[next]falsedistances[next]distances[current]1){distances[next]distances[current]1;}}intmax_distancesMAX_STEPS;for(inti0;in;i)if(visited[i]falsedistances[i]max_distances){currenti;max_distancesdistances[i];}}coutfirst second distances[end]\n;}}return0;}