洛谷P1032字串变换

题目描述
已知有两个字串A,B$A,B$及一组字串变换的规则（至多6个规则）:
A1−>B1$A_1->B_1$
A2−>B2$A_2->B_2$
规则的含义为：在A的子串中A1$A_1$可以变成B1$B_1$，A2$A_2$可以变成B2$B_2$…..
求A$A$变成B$B$所需的最小的转换次数
输入
A1 B1$A_1{B}_1$
A2 B2$A_2{B}_2$
A3 B3$A_3{B}_3$
….
输出
最小的转换次数
例子

abaaaba abcdaba
a b
b d
d e
e f
f g
g c

输出

8

解题思路
广度优先搜索，注意队列里面字符串判重（利用map），熟悉string::find和string::replace用法

#include <iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
struct E{
    string now;
    int cnt;
};
int n=0;
string ori[10],dis[10];
queue<E> Q;
string a,b;
map<string ,int> map1; 
bool bfs(){
    while(!Q.empty()){
        E node=Q.front();
        Q.pop();
        string tmp=node.now;
        if(node.cnt>10){
            cout<<"NO ANSWER!"<<endl;
            return 1;
        }
//      cout<<node.cnt<<endl;

        for(int i=0;i<n;i++){
            for(int pos=tmp.find(ori[i]);pos<tmp.length();pos=tmp.find(ori[i],pos+1)){
            //对ori[i]中的字符串依次判断，找出符合替代的字符串
                if(pos!=string::npos){
                    string tmpstr=tmp;
                    tmpstr.replace(pos,ori[i].length(),dis[i]);
                    if(tmpstr==b){
                        cout<<node.cnt+1<<endl;
                        return 1;
                    }

                    if(!map1.count(tmpstr)){//判重 
                        E nowe;
                        map1[tmpstr]=1;
                        nowe.now=tmpstr;
                        nowe.cnt=node.cnt+1;
                        Q.push(nowe);
                    }
                }
            }
        }
    }
    return 0;
}
/*
s1.find(s2,pos);
s1.replace(pos,s2.size(),s3);
*/

int main(int argc, char** argv) {
    cin>>a>>b;
    while(cin>>ori[n]>>dis[n])
        n++;
    E start;
    start.cnt=0,start.now=a;
    Q.push(start);
    if(!bfs()){
        cout<<"NO ANSWER!"<<endl;
    }
    return 0;
}