总时间限制: 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
在openjudge做的第一道题……单词转化问题，DFS？ 于是兴奋地写了一发……只能拿一半的分……递归边界不好控制啊！ BFS?嗯，又写了一发，A了！
所以记住：字符串最小转化问题要用BFS！而不是DFS！
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; struct Change { string s; int step; }; string s[50]; int len, cnt; bool vis[50]; queue<Change> q; void bfs() { Change c; c.s = s[0], c.step = 0; q.push(c); vis[0] = 1; while(!q.empty()) { Change now = q.front(); q.pop(); for(int i = 1; i <= cnt; i++) { int t = 0; for(int j = 0; j < len; j++) if(now.s[j] != s[i][j]) t++; if(t == 1 && !vis[i]) { vis[i] = 1; Change nxt; nxt.s = s[i], nxt.step = now.step + 1; if(i == cnt) { printf("%d", nxt.step + 1); return; } else q.push(nxt); } } } printf("0"); return ; } int main() { string sn; cin>>s[0]>>sn; len = sn.length(); while(cin>>s[++cnt]); s[cnt] =sn; bfs(); return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017029.html
