#5057. 单词序列 - 题目

时间限制：20 ms 内存限制：128 MiB 输入文件：word.in 输出文件：word.out

题目类型：传统评测方式：文本比较

上传者： Super_Cube

登录后提交提交记录统计讨论题解

本题采用文件输入输出。

输入文件为 word.in，输出文件为word.out。

给出两个单词（开始单词和结束单词）以及一个词典。找出从开始单词转换到结束单词，所需要的最短转换序列。转换的规则如下：

每次只能改变一个字母

转换过程中出现的单词(除开始单词和结束单词)必须存在于词典中

例如：

开始单词为：hit

结束单词为：cog

词典为：[hot,dot,dog,lot,log,mot]

那么一种可能的最短变换是： hit -> hot -> dot -> dog -> cog,

所以返回的结果是序列的长度5；

注意：

如果不能找到这种变换，则输出0；

词典中所有单词长度一样；

所有的单词都由小写字母构成；

开始单词和结束单词可以不在词典中。

从文件 word.in 中读入数据。

共两行

第一行为开始单词和结束单词（两个单词不同），以空格分开。

第二行为若干的单词（各不相同），以空格分隔开来，表示词典。

输出到文件 word.out 中。

输出转换序列的长度。

样例输入

hit cog
hot dot dog lot log

样例输出

30%的数据字符串长度≤4，字典里单词个数≤30，字母是'a'到'd'；

60%的数据字符串长度≤6，字典里单词个数≤100，字母是'a'到'h'；

100%的数据字符串长度≤8，字典里单词个数≤1000，字母是'a'到'z'；

#5057. 单词序列暂未评定