蓝桥杯备考：DFS求最短路之字串变换

这道题我们是可以用BFS做的

我们需要注意3个问题。1.我们怎么记录某个字符串的最短路径？我们可以用哈希表 unordered_map<string,int>

2.我们怎么变换？

这里就要用到我们string的两个接口了，一个是find，一个是substr

我们可以找到可变化的位置，比如bc→xz  如果我们字符串是abcd，那我们find("bc")就返回b的下标了，也就是1，然后我们再拼接一下字符串就行了，假设我们找到的是pos位置，我们就截取0到pos-1位置的子串加上转换的字符串 再截取pos+size()到末尾的子串拼接，就是我们转换后的字符串了

3.如果一个字符串出现了多个同个可转换的子串，怎么办？

我们可以每次find之后把返回的pos++继续找，如果能找到就不断的找

好的，注意事项都说完了，接下来让我们实现一下代码吧！

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 15;
string a,b;
unordered_map<string,int> dist;
int cnt;
string s1[N],s2[N];
int bfs()
{if(a==b) return 0; queue<string> q;q.push(a);dist[a] = 0;while(q.size()){string t = q.front();q.pop();if(dist[t]>=10) continue;if(t==b) return dist[t];for(int i =0;i<cnt;i++){int pos = 0;while(t.find(s1[i],pos)!=-1){pos = t.find(s1[i],pos);string tmp = t.substr(0,pos)+s2[i] +t.substr(pos+s1[i].size());pos++;if(dist.count(tmp)) continue;//如果已经有了，那有的一定是最短路径dist[tmp]=dist[t]+1;q.push(tmp);}}}return -1;
}
int main()
{cin >> a >> b;while(cin >> s1[cnt] >> s2[cnt]){cnt++;}int ret = bfs();if(ret == -1) cout << "NO ANSWER!" << endl;elsecout << ret << endl;return 0;
}