1099 字串變換

?

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 }

?

?

?

轉載于:https://www.cnblogs.com/zwfymqz/p/6764774.html

總結

以上是生活随笔為你收集整理的1099 字串变换 2002年NOIP全国联赛提高组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。