首页 > > 程序设计 > C/C++ >

P1032 字串变换

2018-06-17 22:23:23来源：未知阅读 ()

题目描述

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