问题1665--【USACO】Word Morph(单词接龙)

1665: 【USACO】Word Morph(单词接龙)

时间限制: 1.000 Sec  内存限制: 64 MB
提交: 32  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

Farmer John is playing a word game against his cows. It starts like this: * Farmer John chooses a word, such as 'cat' * The cows then choose their own word, perhaps 'dog' Farmer John then must morph his word to the cows' word by performing a number of steps, each one of which changes one single letter at a time to make a new, valid word. Your program should read a dictionary of valid words from file dict.txt. The file has no more than 25,000 words, each with length in the range 1..20. These 'words' contain only letters in the range 'a'..'z'. The same dictionary is used for all tests. For this example, Farmer John could make the following sequence of four words: 'cat' -> 'cot' -> 'cog' -> 'dog' to morph words from the first word 'cat' to the final word 'dog' in just three moves. The cows will never give Farmer John an impossible task. Farmer John must get from his word to the cows' word in as few moves as possible. You will be given a starting word and an ending word. Determine and output a number which is the least number of legal letter changes required to morph the starting word to the ending word.
/*
农场主约翰正在和他的奶牛们玩一个单词接龙游戏. 这个游戏的规则如下: * 农场主约翰首先选择一个单词, 比如 'cat'
* 然后奶牛们选择一个它们自己的单词, 可能是 'dog' 接下来农场主约翰必须用一定的次数从他的单词接龙到奶牛们的单词, 每一次只能改变一个字母从而接龙出一个新的, 有效的单词. 你的程序要从字典文件dict.txt中读入这些有效的单词. 文件里有25,000个单词, 每一个单词的长度在 1..20 范围内. 这些单词只包含字母 'a'..'z'. 这个用于测试的字典与以往的文件是一样的. 看这个例子, 约翰要接龙出这样的4个单词序列: 'cat' -> 'cot' -> 'cog' -> 'dog' 从第一个单词'cat'接龙到最后一个单词'dog'用了三步. 奶牛们不会给约翰一个不可能的任务. 约翰必须用一些有限的步数从他的单词接龙出可能的单词,直到奶牛们的单词. 你将得到一个开始和结束的单词. 确定并输出从开始单词合法地接龙到结束单词所用的最小的接龙次数.
*/


输入

* Line 1: A single string that is the starting word
* Line 2: A single string that is the end word
/*
* 第1行: 一个字符串表示开始时的单词
* 第2行: 一个字符串表示结束时的单词
*/


输出

* Line 1: A single integer that is the number of times a letter must be changed to transform the starting word into the ending word.
/*
* 第1行: 一个单独的整数表示从开始单词接龙到结束单词所用的最小步数.
*/


样例输入 复制

cat dog

样例输出 复制

3

提示

用到的字典文件在:d:\data\1665\wmorph.dict.txt


来源/分类


[提交] [状态]