【NOIP 2002】 字串变换

【题目链接】

           https://www.luogu.org/problemnew/show/P1032

【算法】

           广度优先搜索

           用stl库里的map来判重

【代码】

           

#include<bits/stdc++.h>
using namespace std;

int n;
string A,B;
string s1[30],s2[30];
map<string,bool> mp;

inline bool bfs()
{
        int i,pos;
        queue< pair<string,int> > q;
        pair<string,int> cur;
        string tmp;
        q.push(make_pair(A,0));
        while (!q.empty())
        {
                cur = q.front();
                q.pop();
                if (cur.second > 10) return false;
                if (cur.first == B)
                {
                        printf("%d
",cur.second);
                        return true;
                }
                for (i = 1; i <= n; i++)    
                {
                        if (cur.first.find(s1[i]) == string :: npos) continue;
                        pos = cur.first.find(s1[i]);
                        while (true)
                        {
                                tmp = cur.first;
                                tmp.replace(pos,s1[i].length(),s2[i]);
                                if (!mp[tmp])
                                {
                                        q.push(make_pair(tmp,cur.second+1));
                                        mp[tmp] = true;
                                }
                                if (cur.first.find(s1[i],pos+1) == string :: npos) break;
                                pos = cur.first.find(s1[i],pos+1);
                        }
                }    
        }        
}

int main() 
{
        
        cin >> A >> B;
        n = 1;
        while (cin >> s1[n] >> s2[n]) n++;
        if (!bfs()) printf("NO ANSWER!
");
                
        return 0;
    
}