[NOIP2002]字串变换 题解

题目链接：字串变换

字符串的题以后还是用string吧，很多函数贼有用。

思路：

双向BFS，判断中途相遇，两个map即可。关键是处理字符串的替换，

找子串可以用string的find()函数，替换可以用string 的 replace()函数.

代码：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
using namespace std;
string a,b,s[25],t[25];
int ans=0x3f3f3f3f,flag,n=1;
void bfs(){
    map<string,int>mp;
    map<string,int>cnt;
    queue<string>q;
    q.push(a);mp[a]=1;cnt[a]=0;
    q.push(b);mp[b]=2;cnt[b]=0;
    while(!q.empty()){
        string sd;
        sd=q.front();
        q.pop();
        if(cnt[sd]>=10)return;
        for(int i=1;i<=n;i++){
            int num=0;
            while(1) {
            num++;
            string qq=sd;
            int pos=qq.find(s[i],num-1);
            if(pos==-1)break;
            qq.replace(pos,s[i].size(),t[i]);
            if(mp[qq]==0){
            mp[qq]=mp[sd];
            cnt[qq]=cnt[sd]+1;
            q.push(qq);
            }
            if(mp[qq]+mp[sd]==3){
                ans=min(ans,cnt[sd]+cnt[qq]+1);
                return;
            }
          }
        }
        
    }
}
int main(){
    cin>>a;cin>>b;
    while(cin>>s[n]>>t[n])
    n++;
    n--;
    bfs();
    if(ans<=10)
    printf("%d",ans);
    else
    printf("NO ANSWER!");
    return 0;
}