时间限制: 1000ms 内存限制: 256MB

描述

Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。 

由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。

输入

输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。

输出

对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。

数据范围

1 ≤ T ≤ 100

小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10 

大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100 

样例输入

1. 2 
2. 4 3 
3. ship sheep 
4. sinking thinking 
5. thinking sinking 
6. the ship is sinking 
7. 10 5 
8. tidy tiny 
9. tiger liar 
10. tired tire 
11. tire bear 
12. liar bear 
13. a tidy tiger is tired 

样例输出

1. Case #1: the sheep is thinking 
2. Case #2: a tiny bear is bear 

代码如下：

1. #include <cstdio> 
2. #include <cstring> 
3. #include <cmath> 
4. #include <string> 
5. #include <iostream> 
6. #include <map> 
7.   
8. using namespace std; 
9.   
10. map<string,string> mm; 
11. char s1[30],s2[30],s[110],*p; 
12. int t,m,n; 
13.   
14. void solve() 
15. { 
16.     int i; 
17.     string str; 
18.     str=p; 
19.     for(i=1;i<n;i++)  
20.     { 
21.         if(mm.count(str)) 
22.             str=mm[str]; 
23.         else 
24.             break; 
25.     }  
26.     cout<<str; 
27. } 
28.   
29. int main() 
30. { 
31.     int i,cnt;scanf("%d%*c",&t); 
32.     for(cnt=1;cnt<=t;cnt++) 
33.     { 
34.         mm.clear(); 
35.         scanf("%d %d%*c",&n,&m); 
36.         for(i=0;i<m;i++) 
37.         { 
38.             scanf("%s %s%*c",s1,s2); 
39.             mm[s1]=s2; 
40.         } 
41.         gets(s); 
42.         printf("Case #%d: ",cnt); 
43.         p=strtok(s," "); 
44.         solve(); 
45.         while((p=strtok(NULL," "))) 
46.         { 
47.             cout<<" "; 
48.             solve(); 
49.         } 
50.         cout<<endl; 
51.     } 
52.   
53.     return 0; 
54. } 

上述代码来自：http://blog.sina.com.cn/s/blog_959bf1d30101evsx.html

另一组代码：

1. #include <stdio.h> 
2. #include <cstring> 
3. #include <vector> 
4. #include <map> 
5.   
6. using namespace std; 
7.   
8.   
9. //字符串分割函数 
10.  std::vector<std::string> split(std::string str,std::string pattern) 
11.  { 
12.      std::string::size_type pos; 
13.      std::vector<std::string> result; 
14.      str+=pattern;//扩展字符串以方便操作 
15.      int size=str.size(); 
16.   
17.      for(int i=0; i<size; i++) 
18.      { 
19.          pos=str.find(pattern,i); 
20.          if(pos<size) 
21.          { 
22.              std::string s=str.substr(i,pos-i); 
23.              result.push_back(s); 
24.              i=pos+pattern.size()-1; 
25.          } 
26.      } 
27.      return result; 
28.  } 
29.   
30. void Update(vector<string> & str,map<string,string> & w_map) 
31. { 
32.     map<string,string>::iterator it; 
33.     for(int i=0;i<str.size();i++) 
34.     { 
35.         it = w_map.find(str[i]); 
36.         if(it != w_map.end()) 
37.         { 
38.             str[i]=it->second; 
39.         } 
40.     } 
41. } 
42.   
43. int main() 
44. { 
45.     int T; 
46.   
47.     while(scanf("%d",&T) == 1) 
48.     { 
49.         for(int x=1;x<=T;x++) 
50.         { 
51.             int N,M; 
52.             map<string,string> words_map; 
53.             string s1,s2; 
54.             string srcWords,tgtWords; 
55.   
56.             scanf("%d%d",&N,&M); 
57.             for(int i=1;i<=M;i++) 
58.             { 
59.                 cin>>s1>>s2; 
60.                 words_map.insert(make_pair(s1,s2)); 
61.             } 
62.             cin.get();//吃掉上一行换行符 
63.             getline(cin,srcWords,'\n'); 
64.             vector<string> singleWord = split(srcWords," "); 
65.   
66.   
67.             for(int i=1;i<=N-1;i++) 
68.             { 
69.                 Update(singleWord,words_map); 
70.             } 
71.             printf("Case #%d: ",x); 
72.             for(int i=0;i<singleWord.size()-1;i++) 
73.                 cout<<singleWord[i]<<" "; 
74.             cout<<singleWord[singleWord.size()-1]<<endl; 
75.         } 
76.   
77.     } 
78.     return 0; 
79. } 

来自：http://blog.csdn.net/xihuanqiqi/article/details/8763444