变形课
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 9165 Accepted Submission(s): 3415
Problem Description
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体. Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
Sample Output
Yes.
Hint
1 #include <stdio.h> 2 #include <string.h> 3 4 const int MAX_NUM = 105; 5 const int MAX_LEN = 105; 6 char word[MAX_NUM][3]; 7 int visit[MAX_NUM]; //标记该字符串是否访问，防止陷入循环 8 int wordCount; //记录单词的个数 9 bool bResult; //判断结果 10 11 void FormatString(char str[]) //取字符串第一个和最后一个字符 12 { 13 int length = strlen(str); 14 word[wordCount][0] = str[0]; 15 word[wordCount][1] = str[length-1]; 16 word[wordCount][2] = '\0'; 17 wordCount++; 18 } 19 20 void dfs(char ch) 21 { 22 if(bResult)return ; 23 if(ch == 'm') 24 { 25 bResult = true; 26 return ; 27 } 28 29 for(int k = 0; k < wordCount; k++) 30 { 31 if(visit[k] == 0 && ch == word[k][0]) 32 { 33 visit[k] = 1; 34 dfs(word[k][1]); 35 visit[k] = 0; 36 } 37 } 38 } 39 40 int main() 41 { 42 char strTemp[MAX_LEN]; 43 while(scanf("%s", strTemp) != EOF) 44 { 45 bResult = false; 46 wordCount = 0; 47 memset(visit, 0, sizeof(visit)); 48 49 FormatString(strTemp); 50 while(true) 51 { 52 scanf("%s", strTemp); 53 if(strTemp[0] == '0')break; 54 FormatString(strTemp); 55 } 56 57 dfs('b'); //从字符'b'开始搜索 58 if(bResult) 59 printf("Yes.\n"); 60 else 61 printf("No.\n"); 62 } 63 return 0; 64 }