2013 編程之美資格賽：傳話遊戲題目解析與代碼

題目描述

Alice 和 Bob 等好友玩傳話遊戲：所有人按順序站成一排，Alice 第一位，Bob 最後一位。Alice 想一句話告訴第二位，依此類推傳到 Bob。因傳話可能出現偏差，遊戲者越多，Bob 聽到的話與 Alice 原話越不同。Alice 收集到詞彙轉換列表，想知道她的話傳到 Bob 時會變成什麼樣子。

輸入格式

• 第一行整數 T，測試資料組數
• 每組第一行兩個整數 N（遊戲者數量）和 M（單詞轉換列表長度）
• 隨後 M 行，每行兩個單詞 a 和 b，表示單詞 a 傳話時一定會變成 b（無重複 a）
• 最後一行包含若干單詞，表示 Alice 所想的句子（總長 ≤ 100 字符）
• 所有單詞僅含小寫字母，長度 ≤ 20，不同時態視為不同單詞
• 不在列表中的單詞永遠不變化

輸出格式

每組測試資料輸出一行 Case #c: s，c 為測試編號，s 為 Bob 聽到的句子。

資料範圍

• 1 ≤ T ≤ 100
• 小數據：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
• 大數據：2 ≤ N ≤ 100, 0 ≤ M ≤ 100

範例輸入/輸出

2 
4 3 
ship sheep 
sinking thinking 
thinking sinking 
the ship is sinking 
10 5 
tidy tiny 
tiger liar 
tired tire 
tire bear 
liar bear 
a tidy tiger is tired 

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

解題代碼（C++）

#include  
#include  
#include  
#include  
#include  
#include 
 
using namespace std; 
 
map mm; 
char s1[30], s2[30], s[110], *p; 
int t, m, n; 
 
void solve() 
{ 
 int i; 
 string str; 
 str = p; 
 for(i = 1; i < n; i++) 
 { 
 if(mm.count(str)) 
 str = mm[str]; 
 else break; 
 } 
 cout << str; 
} 
 
int main() 
{ 
 int i, cnt; scanf("%d%*c", &t); 
 for(cnt = 1; cnt <= t; cnt++) 
 { 
 mm.clear(); 
 scanf("%d %d%*c", &n, &m); 
 for(i = 0; i < m; i++) 
 { 
 scanf("%s %s%*c", s1, s2); 
 mm[s1] = s2; 
 } 
 gets(s); 
 printf("Case #%d: ", cnt); 
 p = strtok(s, " "); 
 solve(); 
 while((p = strtok(NULL, " "))) 
 { 
 cout << " "; 
 solve(); 
 } 
 cout << endl; 
 } 
 return 0; 
} 

另一組使用 vector 和 split 函式的實作也附在文中。