本文主要是介绍(Luogu) P1032 字串变换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接 https://www.luogu.org/problemnew/show/P1032
AC代码
#include<bits/stdc++.h>
using namespace std;
string A,B;
int N=0,maxlen=0,minlen=1e6+5;//maxlen，minlen为最长长度 ，最短长度
string a[7],b[7];
int res=1e6+5;
map <string, int > id;//记录每种字符串出现的次数
void bfs(string tt,int num) {queue<pair<string,int> > q;q.push(make_pair(tt,num));id[tt]++;while(!q.empty()) {pair<string, int > xx;xx=q.front();q.pop();string tt=xx.first;int num=xx.second;if(num!=0 && tt==A) continue; //如果经过变化又变成了A，不用往下考虑了 if(tt.size()+(10-num)*(maxlen-minlen)<B.size()) continue ;//每次都给他将最短的变成从最长的还达不到B长度，不用考虑了 if(num>10) continue ;// 计数达到>10 不用考虑了 if(tt==B) { //到了，更新结束 res=min(res,num);break;}for(int i=0; i<N; ++i) { //a[i]变b[i]，尝试每一种变化 if(tt.size()>=a[i].size()) {for(int j=0; j<=tt.size()-a[i].size(); ++j) {string tmp=tt;//用string太方便了 if(tmp.substr(j,a[i].size()) == a[i] ) {tmp.replace(j,a[i].size(),b[i]);if(id[tmp]++==0) {//如果这种变换没有出现过，入队列 q.push(make_pair(tmp,num+1));}}}}}}}
int main() {cin>>A>>B;string ta,tb;while(cin>>ta>>tb) {a[N]=ta,b[N++]=tb;int xx=tb.size();maxlen=max(xx,maxlen);minlen=min(xx,minlen);}bfs(A,0);if(res==1e6+5) {cout<<"NO ANSWER!"<<endl;} else cout<<res<<endl;return 0;
}
稍微想一下就知道这是一个广搜题，不过需要剪枝一下，不然会T，但是我一开始却用的递归，将广搜写成了深搜，T了以后，加了好几重剪枝，还是T了一个点。（哭了）
string简单操作可以看一下https://blog.csdn.net/TDD_Master/article/details/83184641
这篇关于(Luogu) P1032 字串变换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
