题目链接
- 总时间限制:
- 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 cog hot dot dog lot log
- 样例输出
-
5
分析：
http://www.cnblogs.com/bleopard/p/4066262.html
http://blog.csdn.net/loi__dijiang/article/details/52812774
最朴素的BFS可过。主要是对于字符串的处理。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 6 using namespace std; 7 8 struct Note 9 { 10 string sf; 11 int nus; 12 } d[31]; 13 14 string ks,es; 15 queue<int> q; 16 bool b[31],vis; 17 int length; 18 int sum=0; 19 20 int gs(string x,string y) 21 { 22 int sum=0; 23 for(int i=0;i<length;i++) if(x[i]!=y[i]) sum++; 24 return sum; 25 } 26 27 int main() 28 { 29 cin>>ks>>es; 30 length=ks.size(); 31 int i=1; 32 char ch; 33 d[i].sf=ks; 34 i=2; 35 while(cin>>d[i].sf) i++; 36 d[i].sf=es; 37 q.push(1); 38 while(!q.empty()) 39 { 40 int cur=q.front(); 41 q.pop(); 42 if(d[cur].sf==es) 43 { 44 printf("%d\n",d[cur].nus+1); 45 vis=1; 46 break; 47 } 48 for(int j=1;j<=i;j++) 49 { 50 if(gs(d[cur].sf,d[j].sf)==1&&!b[j]) 51 { 52 d[j].nus=d[cur].nus+1; 53 q.push(j); 54 b[j]=1; 55 } 56 } 57 } 58 if(!vis) printf("0\n"); 59 return 0; 60 }
