3854: 单词接龙

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：6 解决：3

题目描述

在远古的字典王国中，有一种神奇的接龙规则。两个单词可以接龙，当且仅当它们的长度相同，且恰好只有一个字母不同。例如，"hit" 和 "hot" 只差一个 'o'，因此可以接龙。
给定一个字典（包含许多单词）以及两个特殊的单词 beginWord（起始词）和 endWord（目标词）。
你需要找到一条从 beginWord 变换到 endWord 的最短路径，变换需要遵守以下规则：
  1. 每次变换只能改变一个字母。
  2. 变换过程中产生的每一个中间单词，都必须存在于给定的字典 wordList 中。
  3. 起始单词 beginWord 不一定需要在字典中出现，但目标单词 endWord 必须在变换路径的终点出现（即必须在字典中或能通过规则到达）。
你的任务是计算这条最短变换路径上包含的单词总数

输入

输入共三行：
  • 第一行包含一个字符串，表示起始单词 beginWord。
  • 第二行包含一个字符串，表示目标单词 endWord。
  • 第三行包含若干个字符串（用空格分隔），表示字典 wordList 中的所有单词。

输出

输出一行，包含一个整数，表示最短转换序列中的单词数目。如果不存在这样的序列，输出 0。

样例输入 复制 

hit
cog
hot dot dog lot log cog

样例输出 复制 

5

来源/分类

提交提交记录统计露一手!