【题解】洛谷P1032 [NOIP2002TG]字串变换（BFS+字符串）

洛谷P1032：https://www.luogu.org/problemnew/show/P1032

思路

初看题目觉得挺简单的一道题

但是仔细想了一下发现实现代码挺麻烦的

而且2002年的毒瘤输入是什么鬼啊 连组数都没有的真的好吗

这道题参考了题解才完成

需要用到我从来没有用过的map来判重

然后就是广搜+string的一些自带函数运用

PS：这道题本地测试数据时要用Ctrl+Z+回车才可以出ans

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
#define maxn 15
map<string,int> m;//map用来判重 
string a,b;
string c[maxn],d[maxn];
int n,ans;
struct node//自定义结构体方便调用 
{
    string str;//字符串 
    int sum;//步数 
};
queue <node> q;//队列 
string change(const string &str,int i,int j)
{
    string t="";
    if(i+c[j].length()>str.length()) return t;//长度超过就不可以替换 
    for(int k=0;k<c[j].length();k++)//枚举判断是否可以替换 
        if(str[i+k]!=c[j][k]) return t; 
    t=str.substr(0,i);//新串的前面没有改变 
    t+=d[j];//加上替换之后的串 
    t+=str.substr(i+c[j].length());//加上需要替换的串的后面不需要替换的串 
    return t;
}
int main()
{
    cin>>a>>b;
    while(cin>>c[n]>>d[n]) n++;//毒瘤输入 
    node s;
    s.str=a;//初始的串 
    s.sum=0;
    q.push(s);
    while(!q.empty())//BFS 
    {
        node x=q.front();//取出队列头 
        q.pop();//删除头 
        string temp;
        if(m.count(x.str)==1) continue;//判重 
        if(x.str==b) //如果已经满足 
        {
            ans=x.sum;
            break;
        }
        m[x.str]=1;//这种字符串已经尝试过 
        for(int i=0;i<x.str.length();i++)//从头枚举哪里可以替换 
        {
            for(int j=0;j<n;j++)//枚举替换方案 
            {
                temp=change(x.str,i,j);//替换 
                if(temp!="")//如果可以替换 
                {
                    node y;//加入队列 
                    y.str=temp;
                    y.sum=x.sum+1;
                    q.push(y);
                }
            }
        }
    }
    if(ans>10||(!ans))//注意ans同样不能为0 
    cout<<"NO ANSWER!";
    else
    cout<<ans;
}