题解：P1032 [NOIP 2002 提高组] 字串变换

· · 题解

本蒟蒻只会 STL

思路：每次输入字符串都用 map 记录一下，接着 BFS 时，如果在现在正在遍历的字符串中有咱们记录 map 里有的，那就直接变。

注意：必须把此字符串遍历完不然就会 WA !!!

最后放上代码：

#include<bits/stdc++.h>
using namespace std;
string be,en;
set<string> st;
map<string,vector<string>> mp;
map<string,bool> mp1;
int minn=0x3f3f3f3f;
int n=0;
struct node{
    string sss;
    int cs;
};
inline void bfs()
{
    queue<node> q;
    q.push(node{be,0});
    mp1[be]=1;
    while(!q.empty())
    {
        string s=q.front().sss;
        int i=q.front().cs;
        q.pop();
        if(i>=10)continue;
        if(s==en)
        {
            minn=min(minn,i);
            break;
        }
        for(auto x:st)
        {
            for(int k=0;k+x.size()-1<s.size();k++)
            {
                string ss=s;
                if(s.substr(k,x.size())!=x)continue;
                int tmp=k;
                ss.erase(tmp,x.size());
                for(auto t:mp[x])
                {
                    string ssss=ss;
                    ssss.insert(tmp,t);
                    if(mp1[ssss])continue;
                    // if(i==0)cout<<sss<<endl;
                    mp1[ssss]=1;
                    q.push(node{ssss,i+1});
                }
            }
        }
    }
}
int main()
{
    cin>>be>>en;
    string x,y;
    while(cin>>x>>y)
    {
        n++;
        st.insert(x);
        mp[x].push_back(y);
    }
    bfs();
    if(minn==0x3f3f3f3f)cout<<"NO ANSWER!";
    else cout<<minn;
    return 0;
 }