Problem1167--2020DLOI小甲 第六题 单词接龙(3.2)

1167: 2020DLOI小甲 第六题 单词接龙(3.2)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

给定两个单词(beginWord endWord)和一个字典,找到从 beginWord endWord 的最
短转换序列的长度。转换需遵循如下规则:
1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。
说明
:
如果不存在这样的转换序列,返回 0
所有单词具有相同的长度。
所有单词只由小写字母组成。
你可以假设 beginWord endWord 是非空的,且二者不相同。

Input

1 行: 2 个单词 beginWord endWord
2 行:一个正整数 N,不超过 1000
3~3+N-1 行:每行一个单词。
所有单词长度一样且不超过
10

Output

一个整数,表示最短转换序列的长度。

Sample Input Copy

hit cog
6
hot
dog
dot
lot
log
cog

Sample Output Copy

5

HINT

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5

Source/Category