已知有两个字串 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。
输入格式:
键盘输人文件名。文件格式如下:
A B A1 B1 \
A2 B2 |-> 变换规则
... ... /
所有字符串长度的上限为 20。
输出格式:
输出至屏幕。格式如下:
若在 10 步(包含 10步)以内能将 A 变换为 B ,则输出最少的变换步数;否则输出"NO ANSWER!"
输入样例#1:
abcd xyz
abc xu
ud y
y yz
输出样例#1:
3
以前做过这道题,
但是是打表才过的最后一个点。
今天重做了一遍。
才悟到一个真理:
永远不要对STL产生过度依赖!
1 #include<iostream>
2 #include<cstdio>
3 #include<queue>
4 #include<cstring>
5 #include<cstdlib>
6 #include<map>
7 using namespace std;
8 string bg,ed;
9 struct guize
10 {
11 string a,b;
12 }gz[1001];
13 struct node
14 {
15 string zfc;
16 int step;
17 }now,nxt;
18 int num=1;
19 map<string,bool>mp;
20 int tot=0;
21 void bfs()
22 {
23 queue<node>q;
24 now.zfc=bg;now.step=0;
25 q.push(now);
26 while(q.size()!=0)
27 {
28 node p=q.front();
29 //cout<<p.zfc<<"*4654654"<<endl;
30 if(p.zfc==ed)
31 {
32 printf("%d",p.step);
33 exit(0);
34 }
35 if(p.step>10)
36 {
37 printf("NO ANSWER!");
38 exit(0);
39 }
40 q.pop();
41 mp[p.zfc]=1;
42 for(int i=1;i<=num-1;i++)
43 {
44 string tmp=p.zfc;
45 //int where=p.zfc.find(gz[i].a);
46 for(int j=0;j<p.zfc.length();j++)
47 {
48 if(p.zfc[j]==gz[i].a[0])
49 {
50 int flag=0;
51 for(int k=0;k<gz[i].a.length();k++)
52 {
53 tot++;
54 if(tot>=4384380)
55 {
56 printf("NO ANSWER!");
57 exit(0);
58 }
59 if(p.zfc[j+k]!=gz[i].a[k])
60 {
61 flag=1;break;
62 }
63
64
65 }
66 if(flag==0)
67 {
68 int where=j;
69 nxt.zfc=p.zfc.replace(where,gz[i].a.length(),gz[i].b);
70 p.zfc=tmp;
71 if(mp[nxt.zfc]==0)
72 {
73
74 mp[nxt.zfc]=1;
75 nxt.step=p.step+1;
76 //cout<<p.zfc<<"****"<<nxt.zfc<<"***"<<nxt.step<<endl;
77 q.push(nxt);
78 }
79 }
80 }
81 }
82 }
83 }
84 }
85 int main()
86 {
87 freopen("string.in","r",stdin);
88 freopen("string.out","w",stdout);
89 cin>>bg>>ed;
90 while(cin>>gz[num].a>>gz[num].b)
91 num++;
92 //for(int i=1;i<=num-1;i++)
93 // cout<<gz[i].a<<"+++"<<gz[i].b<<endl;
94 bfs();
95 printf("NO ANSWER!");
96 return 0;
97 }