#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

样例输出

5

数据范围与提示

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

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

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