字串变换(bfs)

因为bfs一直不会的缘故，所以今天要认真做几道题练习一下qwq

---

P1032 字串变换

对于这道题很明显就是bfs

可以搜索顺便记录步数

注意要判重 可以用map

输入也要注意

（代码是抄的 因为我太弱了还不熟悉）

//From Luogu Lemoning
#include<bits/stdc++.h>
using namespace std;
string a,b;
string sa[8],sb[8];
map<string ,int >map1;
int l;
queue<string> q;
queue<int> bb; 
int bfs(){
    int m,n;
    string s,ss;
    while(!q.empty()&&q.front()!=b&&bb.front()<=10){
        if(map1[q.front()]==1){//判重
            q.pop();
            bb.pop();
            continue;    
        }
        map1[q.front()]=1;
        for(int i=1;i<=l;i++){
            s=q.front();
            while(1){
                m=s.find(sa[i]);
                if(m==-1) break;
                ss=q.front();
                ss.replace(m,sa[i].size(),sb[i]);
                q.push(ss);
                bb.push(bb.front()+1);
                s[m]='~';//将S里子串sa[i]的第一次出现位置随便换成另一种无关的字符,这样就可以查找到S里子串sa[i]的下一个出现位置
            }
        }
        q.pop();
        bb.pop(); 
    }
    if(q.empty()==1||bb.front()>10) return -1;
    else return bb.front();
}
int main(){
    cin>>a>>b;
    l=1;
    while(cin>>sa[l]>>sb[l]) l++;
    l--;
    if(l==0&&a!=b){
        puts("NO ANSWER!");
        return 0;
    } 
    q.push(a);
    bb.push(0);
    int k=bfs();
    if(k==-1){
        puts("NO ANSWER!");
    }else{
        cout<<k;
    }
    return 0;
}