B$ 及一组字串转变的条条框框,标题汇报 Description

1099 字串转变

 

二零零零年NOIP全国际联盟赛进步组

 时限: 1
s

 空间范围: 127000KB

 标题等级 : 黄金高尔德

题解

 

 

 

难点陈说 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 ANSWE大切诺基!”

样例输入 Sample Input

abcd xyz
abc xu
ud y
y yz

样例输出 萨姆ple 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 }

 

 

 

1099 字串调换

二〇〇三年NOIP全国际结盟赛升高组

时限: 1 s空间限制: 127000 KB标题品级 : 黄金 高尔德

题解

主题材料汇报Description

已知有三个字串 A$, B$ 及一组字串转换的准则:
     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 步以内能将 A$ 调换为 B$ ,则输出最少的调换步数;不然输出”NO
ANSWEWrangler!”

样例输入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 node10 {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;23     bushu[q.front()]=0;24     25     while!=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;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!=-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;}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 }

相关文章

网站地图xml地图