题解 P1032 【字串变换】

MakotoTSK · 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; 
}