Codevs 1099 字串变换

1099 字串变换

2002年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
　　　　　A1$ -> B1$
　　　　　A2$ -> B2$
　　规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
　　　　例如：A$＝'abcd'　B$＝'xyz'
　　变换规则为：
　　　　‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’

　　则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
　　　‘abcd’->‘xud’->‘xy’->‘xyz’

　　共进行了三次变换，使得 A$ 变换为B$。

输入描述 Input Description

输入格式如下：

　　　A$ B$
　　　A1$ B1$ \
　　　A2$ B2$ |-> 变换规则
　　　... ... /
　　所有字符串长度的上限为 20。

输出描述 Output Description

若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"

样例输入 Sample Input

abcd xyz
abc xu
ud y
y yz

样例输出 Sample Output

数据范围及提示 Data Size & Hint

hehe

/*

    宽搜，将每个规则都用一用就好了

    字符串方面的函数不会用不大好办

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

map<string,bool>m;

string d[],e,a[],b[];

int tim[];

int main(){

    int h=,t=;

    cin>>d[]>>e;

    tim[]=;

    int n=;

    while(cin>>a[n]>>b[n])n++;//变换规则

    while(tim[h]<&&tim[h]!=){//到状态h需要的步数

        for(int i=;i<n;i++){//尝试每一种规则

            int pos=d[h].find(a[i]);//找到可替换的字符串在字符串中的位置

            while(pos!=d[h].npos){//npos表示不存在，也就是只要存在可替换的字符串，就去替换它

                d[t]=d[h];

                d[t].replace(pos,a[i].size(),b[i]);

                tim[t]=tim[h]+;

                if(d[t]==e){cout<<tim[h]<<endl;return ;}

                if(m.find(d[t])==m.end())m[d[t++]]=true;

                pos=d[h].find(a[i],pos+);

            }

        }

        h++;

    }

    cout<<"NO ANSWER!"<<endl;

    return ;

}