（4.7算法之搜索）

8468:单词序列

总时间限制: 

1000ms

内存限制: 

1024kB

描述

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

1、每次只能改变一个字母

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

例如：

开始单词为：hit

结束单词为：cog

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

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

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

注意：

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

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

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

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

输入

共两行，第一行为开始单词和结束单词（两个单词不同），以空格分开。第二行为若干的单词（各不相同），以空格分隔开来，表示词典。单词长度不超过5,单词个数不超过30。

输出

输出转换序列的长度。

样例输入

hit coghot dot dog lot log

样例输出

5 分析： 方法1：本题涉及到字符串的处理以及搜索算法。 题目求最短转换序列，果断采用广度优先搜索算法。 代码：

#include
           
            #include
            
             using namespace std;string s0,s1,s[50];int n=1;struct node{    string ss;    int step;}q[300];int m,f[100]={
         0};//判重，即字典中的第i个单词是否出现过 void bfs(){    int head=0,tail=1;    q[1].ss=s0;q[1].step=1;    while (head
             
              >s0>>s1;    m=s0.length();//求串长     while(cin>>s[n])n++;    s[n]=s1;//将目标点作为字典的最后一个单词     bfs();    return 0;}
             
            
           

 方法2：

本题可以使用最短路径来求解

 

建图:

开始单词为起点：0点；

结束单词为目标点：n；

字典中的单词对应得点：1~n-1

如果两个单词中只有一个字符不同，则两点之间的距离为1，否则为无穷大。

floyd算法代码：

#include
           
            #include
            
             using namespace std;string s0,s1,s[50];int n;int map[300][300]={
         {
         0,0}};struct node{    string ss;    int step;}q[300];int m,f[100]={
         0};//判重，即字典中的第i个单词是否出现过 int work(string s3,string s4){    int t=0;    for (int j=0;j
             
              map[i][k]+map[k][j])                     map[i][j]=map[i][k]+map[k][j];}int main(){    cin>>s0>>s1;    m=s0.length();//求串长     s[0]=s0;    n=1;    while(cin>>s[n])n++;    s[n]=s1;//将目标点作为字典的最后一个单词     for (int i=0;i<=n;i++)        for(int j=0;j<=n;j++)            map[i][j]=1000000;    for (int i=0;i<=n;i++){        map[i][i]=1;        for (int j=i+1;j<=n;j++)            if (work(s[i],s[j])==1) {map[i][j]=1;map[j][i]=1;}    }        floyd();    if (map[0][n]<1000000) cout<