1099 字串变换 2002年NOIP全国联赛提高组

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

string判重+删除

map记录步数，，

但是不知道为啥最后一个点过不了？

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<cstdlib>

 #include<map>

 using namespace std;

 string a,b;

 struct node

 {

     string x;

     string y;

 }bc[];

 int num=;

 int step=;

 map<string,int>bushu;

 string pc;//

 int vis[];

 void bfs()

 {

     queue<string>q;

     q.push(a);

     bushu[q.front()]=;

     while(q.size()!=)

     {

         int numm=q.size();

         string p=q.front();

         if(p==b)

                 {

                 printf("%d",bushu[p]);

                 exit();

                 }

         pc=pc+" "+p+" ";

         q.pop();

         for(int i=;i<=num;i++)

         {

             string dd=p;

             string change=p;

             while()

             {

                 int where=change.find(bc[i].x);

                 if(where!=-&&vis[where]==)

                 {

                     vis[where]=;

                     change[where]='*';

                     int l=bc[i].x.length();

                     p.replace(where,l,bc[i].y);

                     if(p==b)

                     {

                     printf("%d",bushu[dd]+);

                     exit();

                     }

                     if(pc.find(p)!=-)continue;// 判重

                     pc=pc+" "+p+" ";

                     bushu[p]=bushu[dd]+;

                     cout<<step<<" "<<bushu[p]<<" "<<p<<endl;

                     if(p==b)

                     {

                     printf("%d",bushu[p]);

                     exit();

                     }

                     else

                     {step++;q.push(p);}

                     if(bushu[p]>)

                     {printf("NO ANSWER!");exit();}

                     p=dd;

                 }

                 else break;

             }

         }

     }

 }

 int main()

 {

     cin>>a>>b;

     while(cin>>bc[num].x>>bc[num].y){num++;}

     bfs();

     printf("NO ANSWER!");

     return ;

 }

巴特西

1099 字串变换 2002年NOIP全国联赛提高组

1099 字串变换

最新文章

热门文章