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
3
数据范围及提示 Data Size & Hint
hehe
string判重+删除
map记录步数,,
但是不知道为啥最后一个点过不了?
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cstring>
5 #include<cstdlib>
6 #include<map>
7 using namespace std;
8 string a,b;
9 struct node
10 {
11 string x;
12 string y;
13 }bc[9];
14 int num=1;
15 int step=0;
16 map<string,int>bushu;
17 string pc;//
18 int vis[101];
19 void bfs()
20 {
21 queue<string>q;
22 q.push(a);
23 bushu[q.front()]=0;
24
25 while(q.size()!=0)
26 {
27 int numm=q.size();
28 string p=q.front();
29 if(p==b)
30 {
31 printf("%d",bushu[p]);
32 exit(0);
33 }
34 pc=pc+" "+p+" ";
35 q.pop();
36 for(int i=1;i<=num;i++)
37 {
38 string dd=p;
39 string change=p;
40 while(1)
41 {
42 int where=change.find(bc[i].x);
43 if(where!=-1&&vis[where]==0)
44 {
45 vis[where]=1;
46 change[where]='*';
47
48 int l=bc[i].x.length();
49 p.replace(where,l,bc[i].y);
50
51 if(p==b)
52 {
53 printf("%d",bushu[dd]+1);
54 exit(0);
55 }
56
57 if(pc.find(p)!=-1)continue;// 判重
58 pc=pc+" "+p+" ";
59
60 bushu[p]=bushu[dd]+1;
61
62 cout<<step<<" "<<bushu[p]<<" "<<p<<endl;
63
64 if(p==b)
65 {
66 printf("%d",bushu[p]);
67 exit(0);
68 }
69 else
70 {step++;q.push(p);}
71 if(bushu[p]>10)
72 {printf("NO ANSWER!");exit(0);}
73 p=dd;
74 }
75 else break;
76 }
77
78 }
79 }
80 }
81 int main()
82 {
83 cin>>a>>b;
84 while(cin>>bc[num].x>>bc[num].y){num++;}
85 bfs();
86 printf("NO ANSWER!");
87 return 0;
88 }