字串变换

题目描述

已知有两个字串 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!"

样例输入

abcd wyz
abc xu
ud y
y yz

样例输出

一道很有水准的爆搜啊！各种库函数各种卡时。。

　　于是正解是双向bfs。。(⊙﹏⊙)b，从起点开始搜，从终点也同时往回搜就好啦（个鬼啊）！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 #include<queue>
 7 using namespace std;
 8 map<string,int>ma;
 9 map<string,int>mb;
10 string a,b;
11 string p[7],d[7];
12 queue<string>q1;
13 queue<string>q2;
14 int cnt1,cnt2,lim,l1=1,l2=1;
15 int num=1,ans=0x7fffffff;
16 void bfs1(){
17     while(l1--){
18             string t=q1.front();q1.pop();
19             int tim=ma[t];
20             for(int i=1;i<num;++i){
21                 int z=p[i].size();
22                 int pos=t.find(p[i],0);
23                 while(pos!=-1){
24                     string tt=t;
25                     tt.replace(pos,z,d[i]);
26                     if(!ma.count(tt)){
27                         ma[tt]=tim+1;
28                         q1.push(tt);
29                         cnt1++;
30                     }
31                     if(mb.count(tt))
32                         ans=min(ans,tim+1+mb[tt]);
33                     pos=t.find(p[i],pos+1);
34                 }
35             }
36         }
37 }
38 void bfs2(){
39     while(l2--){
40         string t=q2.front();q2.pop();
41         int tim=mb[t];
42         for(int i=1;i<num;++i){
43             int z=d[i].size();
44             int pos=t.find(d[i],0);
45             while(pos!=-1){
46                 string tt=t;
47                 tt.replace(pos,z,p[i]);
48                 if(!mb.count(tt)){
49                     mb[tt]=tim+1;
50                     q2.push(tt);
51                     cnt2++;
52                 }
53                 if(ma.count(tt))
54                     ans=min(ans,tim+1+ma[tt]);
55                 pos=t.find(d[i],pos+1);
56             }
57         }
58     }
59 }
60 void search(){
61     ma[a]=0;mb[b]=0;
62     q1.push(a); q2.push(b);
63     while(lim<=5){
64         cnt1=cnt2=0;
65         bfs1();bfs2();
66         if(ans<10) break;
67         l1=cnt1,l2=cnt2,lim++;
68     }
69 }
70 int main(){
71     cin>>a>>b;
72     while(cin>>p[num])
73         cin>>d[num],num++;
74     search();
75     if(ans<=10) printf("%d
",ans);
76     else printf("NO ANSWER!");
77     return 0;
78 }
79