自动搬运

查看原文

来自洛谷，原作者为

	MakotoTSK **

搬运于2025-08-24 21:20:08，当前版本为作者最后更新于2018-12-22 19:53:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法：广度优先搜索

思路：每次字符串入队列后找可以执行的操作（即看一下有没有可以修改的串），把修改之后的字符串入队列，记录修改的次数。

注意：每次找可以修改的串处理完之后要从这个位置继续往后找看这个字符串后面有没有可以修改的子串。

技巧：这个题使用STL可以大幅减少码量。

#include <iostream>
#include <string>
using namespace std;
string a,b;
string ra[7],rb[7];
struct node{
    string cur;//当前字符串
    int cs;//当前已修改次数
}q[2000000];
int main()
{
    cin>>a>>b;
    int i=1;
    while(cin>>ra[i]>>rb[i])
    {
        i++;
    }
    i-=1;
    
    int head=0,tail=1;
    q[tail].cur=a;      //原字符串入队列
    q[tail].cs=0;
    while(head<tail)
    {
        head++;
        if(q[head].cs>10)    //次数大于10输出无解后结束程序
        {
            cout<<"NO ANSWER!"<<endl;
            return 0;
        }
        for(int j=1;j<=i;j++)
        {
            int pos=q[head].cur.find(ra[j],0);
            while(1)//寻找可以修改的子串
            {
                if(pos==-1)//找不到退出
                {
                    break;
                }
                else    //找到之后把字符串修改之后塞进队列，再继续往下找
                {
                    tail++;
                    q[tail].cur=q[head].cur;
                    q[tail].cs=q[head].cs+1;
                    q[tail].cur.replace(pos,ra[j].size(),rb[j]);
                    if(q[tail].cur==b)
                    {
                        cout<<q[tail].cs;
                        return 0;
                    }
                    pos=q[head].cur.find(ra[j],pos+1);
                }
            }
        }
    }
    return 0; 
}